Massive Algorithms: LeetCode - Reorder List (Java)

https://leetcode.com/problems/reorder-list/

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.

我们尝试着看能否写法上简洁一些，上面的第二步是将后半段链表翻转，那么我们其实可以借助栈的后进先出的特性来做，如果我们按顺序将所有的结点压入栈，那么出栈的时候就可以倒序了，实际上就相当于翻转了链表。由于只需将后半段链表翻转，那么我们就要控制出栈结点的个数，还好栈可以直接得到结点的个数，我们减1除以2，就是要出栈结点的个数了。然后我们要做的就是将每次出栈的结点隔一个插入到正确的位置，从而满足题目中要求的顺序，链表插入结点的操作就比较常见了，这里就不多解释了，最后记得断开栈顶元素后面的结点，比如对于 1->2->3->4，栈顶只需出一个结点4，然后加入原链表之后为 1->4->2->3->(4)，因为在原链表中结点3之后是连着结点4的，虽然我们将结点4取出插入到结点1和2之间，但是结点3后面的指针还是连着结点4的，所以我们要断开这个连接，这样才不会出现环，由于此时结点3在栈顶，所以我们直接断开栈顶结点即可，参见代码如下：

    public void reorderList(ListNode head) {
        if (head==null||head.next==null) return;
        Deque<ListNode> stack = new ArrayDeque<ListNode>();
        ListNode ptr=head;
        while (ptr!=null) {
            stack.push(ptr); ptr=ptr.next;
        }
        int cnt=(stack.size()-1)/2;
        ptr=head;
        while (cnt-->0) {
            ListNode top = stack.pop();
            ListNode tmp = ptr.next;
            ptr.next=top;
            top.next=tmp;
            ptr=tmp;
        }
        stack.pop().next=null;
    }

https://leetcode.com/problems/reorder-list/discuss/44992/Java-solution-with-3-steps
http://www.cnblogs.com/grandyang/p/4254860.html

这道链表重排序问题可以拆分为以下三个小问题：

1. 使用快慢指针来找到链表的中点，并将链表从中点处断开，形成两个独立的链表。

2. 将第二个链翻转。

3. 将第二个链表的元素间隔地插入第一个链表中。

This problem can be solved by doing the following:

Break list in the middle to two lists (use fast & slow pointers)
Reverse the order of the second list
Merge two list back together

 public static void reorderList(ListNode head) {
 
  if (head != null && head.next != null) {
 
   ListNode slow = head;
   ListNode fast = head;
 
   //use a fast and slow pointer to break the link to two parts.
   while (fast != null && fast.next != null && fast.next.next!= null) {
    //why need third/second condition?
    System.out.println("pre "+slow.val + " " + fast.val);
    slow = slow.next;
    fast = fast.next.next;
    System.out.println("after " + slow.val + " " + fast.val);
   }
 
   ListNode second = slow.next;
   slow.next = null;// need to close first part
 
   // now should have two lists: head and fast
 
   // reverse order for second part
   second = reverseOrder(second);
 
   ListNode p1 = head;
   ListNode p2 = second;
 
   //merge two lists here
   while (p2 != null) {
    ListNode temp1 = p1.next;
    ListNode temp2 = p2.next;
 
    p1.next = p2;
    p2.next = temp1;  
 
    p1 = temp1;
    p2 = temp2;
   }
  }
 }
 
 public static ListNode reverseOrder(ListNode head) {
 
  if (head == null || head.next == null) {
   return head;
  }
 
  ListNode pre = head;
  ListNode curr = head.next;
 
  while (curr != null) {
   ListNode temp = curr.next;
   curr.next = pre;
   pre = curr;
   curr = temp;
  }
 
  // set head node's next
  head.next = null;
 
  return pre;
 }

Read full article from LeetCode – Reorder List (Java)

LeetCode - Reorder List (Java)

Labels

Popular Posts