Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
分析¶
/** * Given a singly linked list L: L0 → L1 → … → Ln-1 → Ln, * reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … * * You may not modify the values in the list's nodes, * only nodes itself may be changed. * * * Example: * Given 1->2->3->4, reorder it to 1->4->2->3. * Given 1->2->3->4->5, reorder it to 1->5->2->4->3. * * https://leetcode.com/problems/reorder-list/description/ * * 由于后半部分链表需要倒置,所以很显然能直接想到使用stack, * 所以分成三部分: * 1. 找到中点和终点 * 2. 把中点-终点部分放入stack中 * 3. 依次从链表和stack中取出元素,链接起来 * * * */ public class Q143ReorderList { public static void reorderList(ListNode head) { if (head == null || head.next == null) { return; } ListNode mid = head, tail = head.next; boolean odd = false; while ((tail != null) && ( tail.next != null)) { mid = mid.next; tail = tail.next.next; } // 判断链表个数奇偶 if (tail == null) { odd = true; } Stack<ListNode> stack = new Stack<>(); mid = mid.next; while (mid != tail) { stack.push(mid); mid = mid.next; } if (!odd) { stack.push(mid); } ListNode res = new ListNode(0), pos = head; ListNode tmp = res, tmp2; int size = stack.size(); for (int i = 0; i < size ; i++) { tmp2 = pos.next; // store pos next elem res.next = pos; res.next.next = stack.pop(); res = res.next.next; pos = tmp2; // resotre pos next elem } if (odd) { res.next = pos; res = res.next; } res.next = null; head = tmp; } }
近期评论