LeetCode 143 ReoderList_c语言完整实现main函数 将给定的单链表l:l0→l1→l2→…→ln-2→ln-1→ln 重新排

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

• 本题中由于需要改动节点，逆序是需要使用三个节点指针来储存pre,now,next三个地址，开始时将pre->指向NULL
• 将链表分为前后两段时可用快慢指针来确定中位节点位置

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode *head1=head,*temp=head;
        int num=0,flag;
        while(temp)num++,temp=temp->next;
        flag=num%2,num/=2;
        for(int i=0;i<num;i++)head1=head1->next;
        if(head1&&head1->next){//将后半部分逆序
            ListNode *pre=head1,*now=head1->next,*next=head1->next->next;
            head1->next=NULL;
            while(now){
                now->next=pre;
                pre=now,now=next;
                if(next)next=next->next;
            }
            head1=pre;
        }
        
        while(head&&head1&&head->next&&head1->next){
            ListNode* p=head,*p1=head1;
            head=head->next;
            head1=head1->next;
            p->next=p1,p1->next=head;
        }
        if(flag&&head&&head->next)head->next->next=NULL;
        else if(head)head->next=head1,head1->next=NULL;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29