reorder-list java

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}.

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/

给定一个链表，把最后一个结点插入到第1个结点后，倒数第二个结点插入到第2个结点后，倒数第三个结点插入到第3个结点后，以此类推……

【思路】

由题意知，后面 (n-1)/2 个结点需要分别插入到前面 (n-1)/2 个结点后。

那么先把链表分为两段，前面 n-(n-1)/2 个结点为被插入链表，和后面 (n-1)/2 个结点为插入链表。

在插入之前，需先把插入链表逆序，即第n个结点->第n-1个结点->...

【Java代码】

方法1

public class Solution {public void reorderList(ListNode head) {ListNode node = head;int cnt = 0;while (node != null) {cnt++;node = node.next;}if (cnt < 3) return;//3个以下的结点不需要移动int k = (cnt - 1) / 2;//需要移动的后k个结点int i = 1;node = head;while (i++ < cnt - k) {node = node.next;}ListNode begin = node.next;//用begin表示需要移动的后k个结点的开始node.next = null;//把不需要移动的部分结尾设为null//把需要移动的k个结点逆序ListNode pre = begin;ListNode cur = begin.next;begin.next = null;while (cur != null) {ListNode next = cur.next;cur.next = pre;begin = cur;pre = cur;cur = next;}ListNode node1 = head;ListNode node2 = begin;while (node1 != null && node2 != null) {pre = node1;cur = node2;node1 = node1.next;//这两行一定要放在下面两行之前，因为pre和node1指向同一个结点，下面操作会改变node1的next；cur和node2同理node2 = node2.next;cur.next = pre.next;//这两行代码是把cur插入到pre后pre.next = cur;}}
}

方法2

【改进】

先用快慢指针找到链表的中点，然后翻转链表后半部分，再和前半部分组合。

需要注意的是把链表分成两半时，前半段的尾节点要置为NULL，翻转链表时也要把尾节点置为NULL。

public class Solution {public void reorderList(ListNode head) {if (head == null || head.next == null) return;//把整个链表划分成2个等长的子链表，如果原链表长度为奇数，那么第一个子链表的长度多1ListNode slow = head, fast = head;while (fast.next != null) {fast = fast.next;if (fast.next != null) fast = fast.next;else break;slow = slow.next;}ListNode head1 = head, head2 = slow.next;slow.next = null;//翻转第二个子链表ListNode cur = head2, post = cur.next;cur.next = null;while (post != null) {ListNode tmp = post.next;post.next = cur;cur = post;post = tmp;}head2 = cur;//将两个子链表合并ListNode node1 = head1, node2 = head2;while (node2 != null) {ListNode tmp1 = node1.next;ListNode tmp2 = node2.next;node1.next = node2;node2.next = tmp1;node1 = tmp1;node2 = tmp2;}}
}