[leetcode]reorder-list

妖狐艹你老母 2022-03-20 10:06 157阅读 0赞

## 题目描述： ##

Given a singly linked list *L*: *L* 0→*L* 1→…→*L* *n*\-1→*L* n,  
reorder it to: *L* 0→*L* *n* →*L* 1→*L* *n*\-1→*L* 2→*L* *n*\-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\}.

##    实现思路： ##

For example,利用快慢指针找到中间节点，将链表分成前后两段，翻转后半段，然后再将两段合并，前一个后一个前一个后一个……这样子把后半段的插到前半段中去。

## 具体实现： ##

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        void reorderList(ListNode *head) {
            if(!head || !head->next){
                return;
            }
            //快慢指针找到中间节点
            ListNode *fast = head;
            ListNode *slow = head;
            while(fast->next && fast->next->next){
                fast = fast->next->next;
                slow = slow->next;
            }
            //拆分链表，翻转后半部分链表
            ListNode *after = slow->next;
            slow->next = nullptr;
            ListNode *pre = nullptr;
            while(after){
                ListNode *temp = after->next;
                after->next = pre;
                pre = after;
                after = temp;
            }
            //合并两个链表
            ListNode *first = head;
            after = pre;
            while(first && after){
                ListNode *ftemp = first->next;
                ListNode *aftemp = after->next;
                first->next = after;
                first = ftemp;
                after->next = first;
                after = aftemp;
            }
        }
    };

哎喂 对于链表的理解还非常不熟练啊 多练多练呀呀呀！！！

[leetcode]reorder-list

发表评论取消回复

还没有评论，来说两句吧...

相关阅读