Q:将给定的单链表L: L 0→L 1→…→L n-1→L n,重新排序为: L 0→L n →L 1→L n-1→L 2→L n-2→…
要求使用原地算法,并且不改变节点的值
例如:对于给定的单链表{1,2,3,4},将其重新排序为{1,4,2,3}.
A:
链表从中点分割成两个,后面的倒装后,再和前面的merge
public static void reorderList(ListNode head) {
if (head == null || head.next == null)
return;
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
fast = slow.next;
slow.next = null;
ListNode mid = reverse(fast);
merge(head, mid);
}
public static ListNode reverse(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode head0 = new ListNode(Integer.MIN_VALUE);
ListNode node = head;
ListNode node1;
while (node != null) {
node1 = node.next;
node.next = head0.next;
head0.next = node;
node = node1;
}
return head0.next;
}
public static void merge(ListNode head, ListNode mid) {
ListNode node = head;
ListNode node1 = mid;
ListNode node2;
while(node!=null && node1!=null){
node2 = node1.next;
node1.next = node.next;
node.next = node1;
node = node1.next;
node1 = node2;
}
}