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}.
思路
快慢指针切割两端链表，将后面的链表反转插入到前面的链表
反转列表
遍历head，将head.next节点插入到最前面
需要一个headPtr指向起始节点，每次将head插入到起始节点，就需要重新指向head，而又需要遍历下一个节点，则用next记录下下一个要遍历的节点，让head重新指向它。
合并列表
代码
package linkList;
/**
* Created by liqiushi on 2018/1/11.
*/
public class ReorderList {
public void reorderList(ListNode head) {
if (head == null || head.next == null)
return null;
ListNode slow = head;
ListNode fast = head;
// 找到中间结点
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode second = slow.next;
slow.next = null;
second = reverseList(second);
ListNode first = head;
// 把第二个链表插在第一个链表中
ListNode fptr = null;
ListNode sptr = null;
while (second != null) {
fptr = first.next;
sptr = second.next;
first.next = second;
second.next = fptr;
first = fptr;
second = sptr;
}
}
public ListNode reverseList(ListNode head) {
ListNode headPtr = null;
ListNode next = null;
while (head != null) {
next = head.next;
head.next = headPtr;
headPtr = head;
head = next;
}
return headPtr;
}
}
