leetcode121，[leetcode]143. Reorder List

2023-10-08 阅读 29 评论 0

摘要：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. leetcode121？For example,Given?{1,2,3,4}, reorder it to?{1,4,2,3}. ? 看上去有點難，實際

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.

leetcode121？For example,
Given?{1,2,3,4}, reorder it to?{1,4,2,3}.

看上去有點難，實際上可以分為幾個步驟。

LEETCODE？1.找到中間節點。劃分為兩個鏈表。（算法總結里有）

2.把后半部分鏈表反轉。（算法總結里有）

3.合并兩個鏈表。（遞歸）

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* ReverseList(ListNode* head){
12     if(head==NULL||head->next==NULL)
13         return head;
14     ListNode* p=head->next,*q=head,*l=head;
15     while(p->next!=NULL){
16         l=p->next;
17         p->next=q;
18         q=p;
19         p=l;
20     }
21     p->next=q;
22     head->next=NULL;
23     return p;
24 }
25 ListNode* Merge(ListNode* l1,ListNode* l2){
26     if(l1==NULL)
27         return l2;
28     if(l2==NULL){
29         l1->next=NULL;
30         return l1;
31     }
32     ListNode* p=l1,*q=l2;
33     l1=l1->next;
34     l2=l2->next;
35     p->next=q;
36     q->next=Merge(l1,l2);
37     return p;
38 }
39     void reorderList(ListNode* head) {
40         if(head==NULL||head->next==NULL)
41             return;
42         ListNode* p=head,*q=head,*bf=NULL;
43         while(p&&p->next!=NULL){
44             p=p->next->next;
45             bf=q;
46             q=q->next;
47     }
48     bf->next=NULL;
49     q=ReverseList(q);
50     Merge(head,q);
51     return;
52     }
53 };