Question

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.

Thinking:

  • Method 1: O(N)
    • 通过双指针找到中点，将链表的右一半反转。
    • 分别从这两个链表获取结点。
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode pre = null;
        ListNode cur = slow.next;
        ListNode next = null;
        while(cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        slow.next = null;
        while(head != null && pre != null){
            dummy.next = head;
            head = head.next;
            dummy = dummy.next;
            dummy.next = pre;
            dummy = dummy.next;
            pre = pre.next;
        }
        if(head != null) dummy.next = head;
    }
}
  • Method 2: 通过map存储所有的结点。
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        Map<Integer, ListNode> map = new HashMap<>();
        ListNode cur = head;
        int count = 0;
        while(cur != null){
            map.put(count++, cur);
            cur = cur.next;
        }
        ListNode dummy = new ListNode(0);
        ListNode res = dummy;
        int low = 0, high = count - 1;
        while(low <= high){
            dummy.next = map.get(low++);
            dummy = dummy.next;
            dummy.next = map.get(high--);
            dummy = dummy.next;
        }
        dummy.next = null;
    }
}

二刷

二刷想到了一刷的两种方法，最后写的是逆序链表的那个。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode slow = dummy;
        ListNode fast = dummy;
        dummy.next = head;
        while(slow.next != null && fast.next != null){
            slow = slow.next;            
            if(fast.next.next == null)
                break;
            else fast = fast.next.next;
        }
        ListNode pre = null, next = null, cur = slow.next;
        while(cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        slow.next = null;
        cur = dummy;
        while(head != null || pre != null){
            cur.next = head;
            head = head.next;
            cur = cur.next;
            if(pre != null){
                cur.next = pre;
                cur = cur.next;
                pre = pre.next;
            }
        }
        head = dummy.next;
    }
}