leetcode 143 reorder list

Posted by kele on March 31, 2019

leetcode 143 reorder list 笔记

Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

看题目要求很好看懂,就是将一个链表分为两个部分,后面的部分倒序依次插入到前面的链表中。

  1. 因为是将后面的链表倒序放置到前面的链表中,所以想到用堆栈。将所有元素全部遍历一边,同时全部推入到堆栈中。此时可以求出链表的长度 n,循环 n/2 次,分别从堆栈中弹出一个元素,挂到前面的链表中。** 注意 一定要将最后一个链表节点的 next 指针置为空**
  2. 前面的方法中,将所有的元素都推入了堆栈,实际只用到一半的元素。由于多推入了一半的元素,导致入栈时间增多,时间复杂度增加;同时堆栈的规模也增大,所以空间复杂度也增加。所以我们考虑从链表中间开始入栈。

第一种方法

注意代码的鲁棒性,首先检查 head 是否为 NULL ,若为 NULL ,直接跳出函数即可。

/**
 * 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) return ;
        ListNode* p=head,*tmp;
        stack<ListNode*> ss;
        while(p){
            ss.push(p);
            p=p->next;
        }
        int n=ss.size();
        int cnt=0;
        p=head;
        while(cnt<n/2){
            tmp=ss.top();ss.pop();
            tmp->next=p->next;
            p->next=tmp;
            
            p=tmp->next;
            cnt++;        //计数器一开始忘了加!!
        }
        if(n&1) p->next=NULL;  //置链表尾部为空,分为两种情况
        else tmp->next=NULL;
    }
};

第二种方法-从链表中间开始入栈

首先把这种方法分为四步:

  1. 找到链表中间节点
  2. 从中间节点入栈
  3. 从堆栈出栈,插入到前面节点中
  4. 将链表尾置为空,放置成环

找中间链表的方法:

  1. 首先想到的就是将全部节点入栈,获得链表长度之后,出 n/2 的栈元素。但我们要得是直接从中间节点入栈 ❎️
  2. 设置两个链表指针,都指向头部,循环中一个指针每次走一步,另一个指针走两步,最后当第二个指针到达结尾的时候,第一个指针一定刚好到达中点

主要问题解决了,开始上代码:

注意问题:

  1. 代码鲁棒性 head==NULL 时直接返回
  2. 双指针获得链表中点,当链表长度为偶数时,中点指针指向后半部分开头;当链表长度为奇数时,中点指针指向中间节点。所以堆栈中会多入栈一个元素,所以循环的结束条件是 ss.size()>1 ,同时这个多栈的元素恰好是最后一个节点,所以直接 ss.top()->next=NULL 将结尾置空,就可以放置链表成环了。
/**
 * 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) return ;
        ListNode* slow=head,*fast=head;
        while(fast!=NULL&&fast->next!=NULL){
            slow=slow->next;
            fast=fast->next->next;
        }
        stack<ListNode*> ss;
        while(slow){
            ss.push(slow);
            slow=slow->next;
        }
        ListNode* p=head;
        while(ss.size()>1){
            ListNode* tmp=ss.top();ss.pop();
            tmp->next=p->next;
            p->next=tmp;
            
            p=tmp->next;
        }
        ss.top()->next=NULL;
        
    }
};