143.Reorder-List

143. Reorder List

题目地址

https://www.lintcode.com/en/problem/reorder-list/

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.

代码

Approach #1 fast-slow pointer

public class Solution {
    public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    // find middle
    ListNode slow = head, fast = head; // fast = head.next 也能通过！
    while (fast != null && fast.next != null){
      slow = slow.next;
      fast = fast.next.next;
    }
    ListNode rHead = slow.next;
    slow.next = null;

    // reverse ListNode on the right side
    ListNode prev = null;
    while (rHead != null) {
      ListNode temp = rHead.next;
      rHead.next = prev;
      prev = rHead;
      rHead = temp;
    }

    // merge two list
    rHead = prev;
    ListNode lHead = head;
    while (lHead != null && rHead != null){
      ListNode next = lHead.next;
      // add right head
      lHead.next = rHead;
      rHead = rHead.next;
      // update left head 
      lHead.next.next = next;
      lHead = next;
    }

  }
}