L143. Reorder List

LinkedList

Problem:

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.

Solution:

• find the mid

• reverse the list after mid 1 -> 2 -> 4 -> 3

• reverse one by one

findMid function:

• when list.length == even, fast would not be null

  • fast.next != null && fast.next.next != null

  fast would be null

  • fast != null && fast.next !=null

public void reorderList(ListNode head){
    if(head == null || head.next == null) return;
    //find mid
    ListNode slow = head, fast = head;
    while(fast.next != null && fast.next.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    // reverse list after mid
    ListNode preMid = slow;
    ListNode preCur = slow.next;
    while(preCur.next != null){
        ListNode cur = preCur.next;
        preCur.next = cur.next;
        cur.next = preMid.next;
        preMid.next = cur;
    }
    //reverse one by one
    p1 = head;
    p2 = preMid.next;
    while(p2 != preMid){
        preMid.next = p2.next;
        p2.next = p1.next;
        p1.next = p2;
        p1 = p2.next;
        p2 = preMid.next;
    }
}