452
技術社區[雲棲]
[LeetCode]143.Reorder List
【題目】
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}.
【題意】
給定一個單鏈表L：L0→L1→...→LN-1→LN，
它重新排列到：L0→LN→L1→LN-1→L2→LN-2→...
【分析】
題目規定要 in-place，也就是說隻能使用 O(1) 的空間。
可以找到中間節點，斷開，把後半截單鏈表 reverse 一下，再合並兩個單鏈表。
【代碼】
/*********************************
* 日期：2014-01-31
* 作者：SJF0115
* 題目: 143.Reorder List
* 網址：https://oj.leetcode.com/problems/reorder-list/
* 結果：AC
* 來源：LeetCode
* 總結：
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* reorderList(ListNode *head) {
if(head == NULL || head->next == NULL){
return head;
}
//找中間節點
ListNode *slow = head,*fast = head,*pre = NULL,*pre2 = NULL,*temp = NULL;
while(fast != NULL && fast->next != NULL){
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
//在中間截斷成兩個單鏈表
pre->next = NULL;
ListNode *head2 = reverse(slow);
//合並
pre = head;
pre2 = head2;
while(pre->next != NULL){
temp = pre2->next;
//合並
pre2->next = pre->next;
pre->next = pre2;
//下一個元素
pre = pre->next->next;
pre2 = temp;
}
pre->next = pre2;
return head;
}
private:
ListNode* reverse(ListNode *head){
if(head == NULL || head->next == NULL){
return head;
}
ListNode *dummy = (ListNode*)malloc(sizeof(ListNode));
dummy->next = head;
ListNode *tail = head,*cur = head->next;
while(cur != NULL){
//刪除cur元素
tail->next = cur->next;
//插入
cur->next = dummy->next;
dummy->next = cur;
cur = tail->next;
}
return dummy->next;
}
};
int main() {
Solution solution;
int A[] = {1,2,3,4,5,6};
ListNode *head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
ListNode *node;
ListNode *pre = head;
for(int i = 0;i < 6;i++){
node = (ListNode*)malloc(sizeof(ListNode));
node->val = A[i];
node->next = NULL;
pre->next = node;
pre = node;
}
head = solution.reorderList(head->next);
while(head != NULL){
printf("%d ",head->val);
head = head->next;
}
//printf("Result:%d\n",result);
return 0;
}
【溫故】
/*------------------------------------------------------
* 日期：2014-04-09
* 作者：SJF0115
* 題目: 143.Reorder List
* 網址：https://oj.leetcode.com/problems/reorder-list/
* 結果：AC
* 來源：LeetCode
* 總結：
--------------------------------------------------------*/
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* reorderList(ListNode *head) {
if(head == nullptr || head->next == nullptr){
return head;
}//if
// 尋找中間節點
ListNode *slow = head,*fast = head;
while(fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;
}//while
// 從中間節點截斷，分成兩個子鏈表
ListNode *head2 = slow->next;
slow->next = nullptr;
head2 = Reverse(head2);
// 合並
slow = head;
fast = head2;
ListNode *nextNode;
while(slow->next){
nextNode = fast->next;
// 連接到前半鏈表
fast->next = slow->next;
slow->next = fast;
// 更新鏈表指針
slow = slow->next->next;
fast = nextNode;
}//while
slow->next = fast;
return head;
}
private:
ListNode* Reverse(ListNode* head){
if(head == nullptr){
return nullptr;
}//if
// 頭結點
ListNode* dummy = new ListNode(0);
ListNode* cur = head,*nextNode = nullptr;
while(cur){
nextNode = cur->next;
// 頭插入法
cur->next = dummy->next;
dummy->next = cur;
cur = nextNode;
}//while
return dummy->next;
}
};
int main() {
Solution solution;
int A[] = {1,2,3,4,5,6};
ListNode* head = new ListNode(-1);
ListNode *pre = head,*node;
for(int i = 0;i < 6;i++){
node = new ListNode(A[i]);
pre->next = node;
pre = node;
}//for
head = solution.reorderList(head->next);
while(head != NULL){
cout<<head->val<<" ";
head = head->next;
}//while
cout<<endl;
return 0;
}
最後更新：2017-04-03 12:54:53