LeetCode -- Reorder List

LeetCode -- 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 must do this in-place without altering the nodes' values.


For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.


本題算是鏈表中很有特點的一道題目。對於鏈表1->2->3->4->5->6 ，要變成1->6->2->5->3->4，
即第i個節點指向倒數第i個節點，而倒數第i個節點，指向第i+1個節點。



解法一：
使用前後兩個指針p和q。
具體實現步驟在注釋中有詳細說明，在此不再贅述。




由於時間復雜度為O(N^2)，不夠高效導致會超時。無法通過OJ的測試數據。


實現代碼：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void ReorderList(ListNode head) 
    {
        if(head == null || head.next == null || head.next.next == null){
    		return;
    	}
    	
    	var p = head;
    	var q = head;
    	while(q.next.next != null){
    		while(p.next.next != null){
    			p = p.next;
    		}
    		
    		// point head to last
    		var t = q.next;
    		q.next = p.next;
    		// point last to 2nd and set the second last to null
    		p.next.next = t;
    		
    		// point 2nd last to null
    		p.next = null;
    
    		// reset p and q
    		p = t;
    		q = t;
    		if(q.next == null){
    			break;
    		}
    	}
    }
}

解法二：

 



1.使用slow和fast指針將鏈表分為兩部分，part1和part2 ，假設鏈表為1->2->3->4->5->6->7->8, part1 = {1->2->3->4} , part2= {5->6->7->8}
2.然後對part2逆置,即8->7->6->5
3.然後分別將part1[0]->part2[0], part2[0]->part1[1], part1[1]->part2[1]...
即，對於i < len - 1
part1[i] -> part2[i]
part2[i] -> part1[i+1]
i++


實現代碼：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void ReorderList(ListNode head) 
    {
        if(head == null || head.next == null || head.next.next == null){
    		return;
    	}
    	
    	var slow = head;
    	var fast = head;
    	while(fast.next != null && fast.next.next != null)
    	{
    		slow = slow.next;
    		fast = fast.next.next;
    	}
    	
    	var mid = slow.next;
    	var last = mid;
    	ListNode pre = null;
    	while(last != null){
    		ListNode next = last.next;
    		last.next = pre;
    		pre = last;
    		last = next;
    	}
    	slow.next = null;
    	
    	while(head != null && pre != null)
    	{
    		var next1 = head.next;
    		head.next = pre;
    		pre = pre.next;
    		head.next.next = next1;
    		head = next1;
    	}
    }
}