題目143. 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}
思路:使用快慢指針找到鏈表的中點,然后將后半部分插入前半部分
public class Solution {
public void reorderList(ListNode head) {
if(head == null || head.next == null || head.next.next == null){
return ;
}
ListNode lowerNode = head;
ListNode fastNode = head;
while(fastNode.next != null && fastNode.next.next != null){
lowerNode = lowerNode.next;
fastNode = fastNode.next.next;
}
ListNode secondNode = lowerNode.next;
lowerNode.next = null;
ListNode secondHead = new ListNode(1);
ListNode tempNode = null;
while(secondNode != null){
tempNode = secondNode.next;
secondNode.next = secondHead.next;
secondHead.next = secondNode;
secondNode = tempNode;
}
secondNode = secondHead.next;
ListNode firstNode = head;
ListNode tempFirst = null;
ListNode tempSecond = null;
while(secondNode != null){
tempFirst = firstNode.next;
tempSecond = secondNode.next;
secondNode.next = firstNode.next;
firstNode.next = secondNode;
firstNode = tempFirst;
secondNode = tempSecond;
}
}
}
