博文中会简要介绍Leetcode P0143题目分析及解题思路。
“Reorder List”这道题比较经典，也有两种主要思路，第一种思路是以空间换时间，首先遍历一遍链表把所有结点按序存入数组，然后通过头尾相向遍历数组来得到最终结果。上述算法在C++中实现了。
第二种思路是借鉴了翻转链表的想法，将链表的后半部分翻转，然后分别从头结点和中间结点开始遍历，交替连接即可。
Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify the values in the list’s nodes, only nodes itself may be changed.
以下是Java的题解代码实现。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
// Corner case: null or only one node
if (head == null || head.next == null)
return;
// Combination of Reverse Linked List I & II
// First, we find the middle of the list
ListNode half = null, curr = head, fast = head.next;
while (fast != null && fast.next != null) {
curr = curr.next;
fast = fast.next.next;
}
half = curr.next;
curr.next = null;
// Then, we reverse the second half of the list
ListNode dummy = new ListNode(0, half);
ListNode post = half, prev = dummy;
curr = half;
while (post != null) {
post = curr.next;
// Reverse
curr.next = prev;
prev = curr;
curr = post;
}
dummy.next.next = null;
dummy.next = prev;
// Finally, we reorder the list
ListNode l1 = head, l2 = dummy.next;
int flag = 1;
while (l1 != null && l2 != null) {
ListNode next = l1.next;
l1.next = l2;
l1 = next;
next = l2.next;
l2.next = l1;
l2 = next;
}
}
}
以下是C++的题解代码实现。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if (!head)
return;
vector<ListNode*> node_vector;
ListNode *curr = head;
while (curr) {
node_vector.push_back(curr);
curr = curr->next;
}
int len = node_vector.size(), itr = 0;
for (; itr<len/2; ++itr) {
node_vector[itr]->next = node_vector[len-1-itr];
node_vector[len-1-itr]->next = node_vector[itr+1];
}
node_vector[itr]->next = nullptr;
}
};