Description
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}.
Solution
Two-pointers
蛮简单的题，是几道题目的综合，思路如下：
- 将链表平均分成两半（快慢指针）；
- reverse后一个链表；
- merge两个链表。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode secondHead = slow.next;
slow.next = null;
secondHead = reverse(secondHead);
mergeList(head, secondHead);
}
public ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
public ListNode mergeList(ListNode p, ListNode q) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (q != null) {
tail.next = p;
p = p.next;
tail.next.next = q;
q = q.next;
tail = tail.next.next;
}
tail.next = p;
return dummy.next;
}
}
