【LeetCode】Reorder List
來源：程序員人生 發布時間：2014-10-12 19:35:51 閱讀次數：2888次
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代碼】
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;
}
}
}
【感受】
代碼寫起來超惡心，寫著寫著就混亂了，一會兒就不知道next指的是哪個結點了。
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
