LeetCode-链表

作者: raincoffee | 来源:发表于2019-11-06 19:38 被阅读0次

LeetCode-链表

链表（Linked List）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针（Pointer）。

image-20191105225333488

由于不必须按顺序存储，链表在插入的时候可以达到 O(1)O(1) 的复杂度，比另一种线性表 —— 顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n)O(n) 的时间，而顺序表相应的时间复杂度分别是 O(log\ n)O(log n) 和 O(1)O(1)。

对于链表相关的问题，应该注意以下几点：

头节点的使用，即dummyNode的使用，可以减少边界条件判断。涉及到头节点的操作，比如可能删除head等等，使用dummyNode可以减少判断。最后返回dummyNode.next
创建新的节点时，注意在栈上分配对象，如果使用new 需要delete。ps：后续一些题解没有及时更正该方面的问题。
快慢指针。多用于寻找中间节点等，衍生问题环形链表等。主要在于在O(N)的时间来快速获取到想要的节点。

使用快慢指针查找中间节点时，当fast和slow都指向head和slow指向head，fast指向head->next 获取到的中间节点及边界条件不一致，需要注意。
cut函数，cut(ListNode* node,int k) 将链表前k个值切割，返回第k+1个node；多用于分隔链表。
反转链表，需要pre=null,cur=head,next 三个指针，每次进行更新，最后返回pre。
合并链表，注意dummyNode的使用以及边界判空。
删除节点，删除当前节点，可以将下个节点的值复制给当前节点，并指向下下个节点。另一种思路时需要找到删除节点的前驱。
时间复杂度，可以考虑一些辅助工作，如map，stack，set等。
另一个就是链表和排序算法以及树的遍历的结合。归并排序，dfs等等。可以等后续章节进行分析。
链表相关的问题也可以考虑递归的方式进行解决。从而简化问题。

下面介绍LeetCode常见的链表问题。

1.反转链表

206.反转链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head==NULL || head->next==NULL){
            return head;
        }
        ListNode* pre=NULL;
        ListNode* cur=head;
        ListNode* next;
        while(cur){
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};

92.反转链表II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (head==NULL || head->next==NULL){
            return head;
        }
        ListNode* pre=NULL;
        ListNode* cur=head;
        ListNode* next;
        while(m>1){
            pre=cur;
            cur=cur->next;
            m--;
            n--;
        }
        // 需要记录下pre 和 tail；即反转后的头节点和尾节点
        ListNode* con = pre; //反转后的头节点
        ListNode* tail=cur; // 反转后的尾节点
        while(n>0){
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
            n--;
        }
        if(con){
            con->next=pre; //进行连接            
        }else{
            head=pre; //此时证明从第一个节点开始反转，那么头节点直接就是反转后的头节点
        }
        tail->next=cur; //尾节点的next设置为下一个节点cur
        return head;
    }
};

2.删除元素

237.删除链表中的节点

class Solution {
public:
    void deleteNode(ListNode* node) {
        //struct ListNode* tmp=node->next;
        node->val=node->next->val;
        node->next=node->next->next;
        //delete tmp;
    }
};

203.移除链表元素

删除链表中等于给定值 *val* 的所有节点。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head==NULL){
            return NULL;
        }
        struct ListNode* t=new ListNode(-1);
        t->next=head;
        
        struct ListNode* pre=t;
        while(pre->next!=NULL){
            if (pre->next->val==val){
                auto s=pre->next;
                pre->next=pre->next->next;   
                delete s;
            }else{
                pre=pre->next;
            }
        }
        return t->next;
    }
};

19.删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head==NULL || head->next==NULL){
            return NULL;
        }
        ListNode* first=head;
        ListNode* second=head;
        int i=0;
        // 先走n步，找到需要删除的pre节点。
        while(i<n){ 
            first=first->next;
            i++;
        }
        //主要为了判断是否是删除首元素
        if(!first){
            return head -> next;    
        }
        while(first->next!=NULL){
            first=first->next;
            second=second->next;
        }
        ListNode* tmp=second->next;
        second->next=second->next->next;
        delete tmp;
        return head;
    }
};

83.删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* cur=head;
        while(cur!=NULL &&cur->next!=NULL){
            if(cur->next->val==cur->val){
                cur->next=cur->next->next;
            }else{
                cur=cur->next;
            }
        }
        return head;
        
    }
};

82.删除排序链表中的重复元素II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

提示：需要两个指针；一个用来遍历，另一个用来删除。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode dummyNode(-1);
        ListNode* pre=&dummyNode;
        ListNode* cur=head;
        ListNode* tmp;
        int n,val;
        while(cur){
            tmp = cur;
            for(n=0,val=cur->val;cur!=NULL && cur->val==val;++n){
                cur=cur->next;
            }
            if (n==1){
                pre->next=tmp;
                pre=pre->next;
            }
        }
        pre->next=NULL;
        return dummyNode.next;
        
    }
};

1171.从链表中删去总和值为0的连续节点

给你一个链表的头节点 head，请你编写代码，反复删去链表中由总和值为 0 的连续节点组成的序列，直到不存在这样的序列为止。删除完毕后，请你返回最终结果链表的头节点。

你可以返回任何满足题目要求的答案。（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

提示：我们可以考虑如果给的入参不是链表是数组的话，只需要求出前缀和，对于前缀和相同的项，那他们中间的部分即是可以消除掉的，比如以 [1, 2, 3, -3, 4] 为例，其前缀和数组为 [1, 3, 6, 3, 7] ，我们发现有两项均为 3，则 6 和第二个 3 所对应的原数组中的数字是可以消掉的。换成链表其实也是一样的思路，把第一个 3 的 next 指向第二个 3 的 next 即可。

示例 1：

输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        // 求和，当出现重复是 证明两个重复节点之间的数据可以被删除；
        // 然后继续递归； 返回值为dummy->next；
        if (head==NULL){
            return head;
        }
        ListNode dummy(0);
        dummy.next=head;
        ListNode* dummyPtr=&dummy;
        map<int,ListNode*> map;
        map[0]=dummyPtr;
        int sum=0;
        while(head!=NULL){
            sum+=head->val;
            if(map.find(sum)!=map.end()){
                map[sum]->next=head->next;
                return removeZeroSumSublists(dummy.next);
            }else{
                map[sum]=head;
                head=head->next;
            }
        }
        return dummy.next;   
    }
};

3.合并链表

合并链表，需要注意头节点dummyNode的使用。另外为了降低复杂度，可以考虑使用归并算法。

21.合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy = ListNode(-1);  //  创建栈空间对象即可。
        ListNode* prev = &dummy;   // 注意这里需要取地址&
        while(l1 != NULL && l2 != NULL) {
            if(l1->val <= l2->val) {
                prev->next = l1;
                l1 = l1->next;
            } else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }
        prev->next = l1 != NULL ? l1 : l2;
        return dummy.next;
    }
};

23.合并K个有序链表

题解：已经实现了合并两个有序链表了，那么其实可以使用归并的思想进行合并k个链表，两两合并，时间复杂度为Nlogk

ListNode* mergeKLists(vector<ListNode*>& lists) {
        int len = lists.size();
        if(len < 1) return NULL;
        while(len>1){
            int m = (len + 1) / 2;
            for(int i=0;i<m && i+m < len;++i){
                lists[i] = mergeTwoLists(lists[i],lists[i+m]);
            }
            len = m;
        }
        return lists[0];
    }

2. 两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

题解：新的节点等与两个节点的(val+进位)%10; 下一轮的进位为(val+进位)/10；

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *root=new ListNode(0);
        ListNode *cur=root;
        ListNode *tmp;
        int c=0;
        while(l1!=NULL || l2!=NULL || c!=0){ //注意边界条件，可能最后只有进位，需要创建新的节点
            int v1=l1?l1->val:0;
            int v2=l2?l2->val:0;
            int sum=v1+v2+c;
            c=sum/10;
            tmp=new ListNode(sum%10);
            cur->next=tmp;
            cur=tmp;
            if (l1){
                l1=l1->next; // 注意边界条件
            }
            if (l2){
                l2=l2->next;
            }
        }
        return root->next;
    }
};

445.两数相加II

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶:如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例:

输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

题解：当当前值的计算依赖下一项的计算时，可以使用递归的方法来实现回溯。当前值=（val+下一项的进位）/10。需要两个链表等长。另一种办法是借助额外的结构，来实现。例如栈/数组等。

class Solution {
public:
   ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        vector<ListNode*> l1v,l2v;
        to_vector(l1,l1v);
        to_vector(l2,l2v);
        int i=l1v.size()-1, j=l2v.size()-1;
        int d = 0;
        ListNode *head = NULL;
        while(i >= 0 || j >= 0){
            if(i >= 0) d += l1v[i--]->val;
            if(j >= 0) d += l2v[j--]->val;
            ListNode* p = new ListNode(d%10);
            p->next = head;
            head = p;
            d /= 10;
        }
        if(d) {
            ListNode* p = new ListNode(d);
            p->next = head;
            head = p;
        }
        return head;
    }
    
    void to_vector(ListNode* a,vector<ListNode*>& v){
        while(a){
            v.push_back(a);
            a = a->next;
        }
    }
};

4.重排链表

链表按照指定的规则进行重新排序。比如首尾相连，交换链表节点等等。

24.两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

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

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

题解：声明dummyNode，pre指向dummy。 start指向1，end指向2. 让pre.next=end;start.next=end.next;end.next=start. pre此刻再向前移动到start。

class Solution {
   public ListNode swapPairs(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode temp = pre;
        while(temp.next != null && temp.next.next != null) {
            ListNode start = temp.next;
            ListNode end = temp.next.next;
            temp.next = end;
            start.next = end.next;
            end.next = start;
            temp = start;
        }
        return pre.next;
    }
}

25. k个一组反转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 :

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

题解：合理利用cut函数，每k个一组，切割成链表，然后反转，然后注意进行链接。每次反转前判断下长度是否达到k。当对头节点有进行操作是，注意使用dummyNode。主要要保持链表直接的连接。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
         ListNode dummyHead(0);
         dummyHead.next=head;
         auto cur=dummyHead.next;
         auto tail = &dummyHead;
         while(cur){
            auto left = cur;
            cur = cut(left, k); // left->@->@ right->@->@->@...
            tail->next = reverseList(left,k);
            while(tail->next){
                tail=tail->next;
            }
        }
        return dummyHead.next;
    }
    
    // k个一组进行反转，采用cut函数，连接的时候，注意保证尾部正确。
    
    ListNode* cut(ListNode* head,int k){
        auto p=head;
        while(--k && p){
            p=p->next;
        }
        if(!p){
            return nullptr;
        }
        auto next=p->next;
        p->next=nullptr;
        return next;
    }
    
    ListNode* reverseList(ListNode* head,int k) {
        struct ListNode* p=head;
        while(p!=NULL){
            p=p->next;
            k--;
        }
        if (k>0){
            return head;
        }
        struct ListNode* pre=NULL;
        struct ListNode* cur=head;
        struct ListNode* tmp=NULL;
        while(cur){
            tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
};

61.旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

题解：方法一：先连接，再旋转。再断开。方法二：可以先整体逆序，然后前k个逆序，后n-k个逆序。

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL){
            return NULL;
        }
        if (head->next==NULL){
            return head;
        }
        ListNode *cur=head;
        int n=1;
        while(cur->next!=NULL){
            cur=cur->next;
            n++;
        }
        cur->next=head;
        ListNode *new_tail = head;
        int i=0;
        for(i=0;i<n - k % n - 1;++i){
            new_tail=new_tail->next;
        }
        ListNode* tmp=new_tail->next;
        new_tail->next=NULL;
        return tmp;
    }
};

143.重排链表

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

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

给定链表 1->2->3->4, 重新排列为 1->4->2->3.
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

经典问题：考察快慢指针找中间节点；分隔链表；链表反转，链表合并。需要考虑将中间节点分配到第一个链表还是第二个链表。考虑清楚边界条件。

class Solution {
public:
    void reorderList(ListNode* head) {
        // 先快慢指针找到中间节点，然后对后面的反转，最后合并
        if(head==NULL || head->next==NULL){
            return ;
        }
        ListNode* slow=head;
        ListNode* fast=head->next;
        while(fast!=NULL && fast->next!=NULL){
            fast=fast->next->next;
            slow=slow->next;
        }
        ListNode* l2=slow->next;
        slow->next=NULL;
        ListNode* l1=head;
        // 反转list2
        ListNode* pre=NULL;
        ListNode* cur=l2;
        ListNode* next;
        while(cur!=NULL){
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        l2=pre;
        // 合并l1 l2
        while(l2!=NULL){
            slow=l1->next;
            fast=l2->next;
            l1->next=l2;
            l2->next=slow;
            l1=slow;
            l2=fast;
        }
        return;
    }
};

147.链表进行插入排序

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode h(-1);
        h.next = head;
        ListNode* pre = &h;
        ListNode* cur = head;
        ListNode* lat;
        ListNode* tmp;
        while (cur != NULL) {
            lat = cur->next; // 记录下一个要插入排序的值
            if (lat != NULL && lat->val < cur->val) { 
                // 只有 cur.next 比 cur 小才需要向前寻找插入点
                while (pre->next != NULL && pre->next->val < lat->val) { 
                    pre = pre->next; // 继续向后移动
                }
                // 找到要插入的位置，此时 pre 节点后面的位置就是 lat 要插入的位置
                tmp = pre->next;
                pre->next = lat;
                cur->next = lat->next;// 保证cur不断
                lat->next = tmp;
                pre = &h;// 由于每次都是从前往后找插入位置，所以需要每次插入完成后要让 pre 复位
            } else {
                // 都这直接把 cur 指针指向到下一个
                cur = lat;
            }
        }
       return h.next;
    }
};

148.排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

题解：要求时间复杂度，考虑到归并排序。两两合并，需要logn次。每次进行n个比较。需要注意的点；cut函数实现，合并链个有序链表；dummyNode使用；链表的连接；等等。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode dummyHead(0);
        dummyHead.next=head;
        auto p=head;
        int length=len(p);
        for (int size=1;size<length;size<<=1){
            auto cur=dummyHead.next;
            auto tail = &dummyHead;
            while(cur){
                 auto left = cur;
                 auto right = cut(left, size); // left->@->@ right->@->@->@...
                 cur = cut(right, size); // left->@->@ right->@->@  cur->@->..
                 tail->next = merge(left, right);
                while(tail->next){
                    tail=tail->next;
                }
            }
        }
        return dummyHead.next;
    }
    
    int len(ListNode *p){
        int length=0;
         while (p) {
            ++length;
            p = p->next;
        }
        return length;
    }
    
    ListNode* cut(ListNode* head,int n ){
        auto p=head;
        while(--n && p){
            p=p->next;
        }
        if(!p){
            return nullptr;
        }
        auto next=p->next;
        p->next=nullptr;
        return next;
    }
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummyHead(0);
        auto p = &dummyHead;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                p->next = l1;
                p = l1;
                l1 = l1->next;       
            } else {
                p->next = l2;
                p = l2;
                l2 = l2->next;
            }
        }
        p->next = l1 ? l1 : l2;
        return dummyHead.next;
    }
};

5.分隔链表

86.分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

题解：分解成两个链表，再连接。注意dummyNode的使用。

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (head==NULL ||head->next==NULL){
            return head;
        }            
        ListNode l_head(-1);
        ListNode r_head(-1);
        ListNode* l=&l_head;
        ListNode* r=&r_head;
        auto l_tmp=l;
        auto r_tmp=r;
        while(head!=NULL){
            if(head->val<x){
                l->next=head;
                l=l->next;
            }else{
                r->next=head;
                r=r->next;
            }
            head=head->next;
        }
        l->next=r_tmp->next;
        r->next=NULL;
        return l_tmp->next;
    }
};

109.有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

题解：二叉搜索树的前序遍历为有序数组。那么对于链表中间节点即为跟节点。采用递归进行遍历即可。

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        //核心思想，中心节点就是根节点，递归构造左右子节点。
        if(head==NULL){
            return NULL;
        }
        ListNode* mid=getMidNode(head);
        TreeNode* node=new TreeNode(mid->val);
        if (head==mid){
            return node;
        }
        node->left=sortedListToBST(head);
        node->right=sortedListToBST(mid->next);
        return node;
    }
    // 查找中间节点并返回。并分割left链表最后指向NULL。
    ListNode* getMidNode(ListNode *head){
        ListNode* pre=NULL;
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast!=NULL && fast->next!=NULL){
            pre=slow;
            slow=slow->next;
            fast=fast->next->next;
        }
        if (pre!=NULL){
            pre->next=NULL;
        }
        return slow;
        
    }
   
};

725.分隔链表

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。

这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。

返回一个符合上述规则的链表的列表。

举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]

示例 1：

输入: 
root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]
解释:
输入输出各部分都应该是链表，而不是数组。
例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。
示例 2：

输入: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解释:
输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* root, int k) {
        // 遍历root的长度，得到len。 
        // if len<=k ; 那么每个都是独立节点，再增加k-len个空节点。
        // if len>k; 那么切分为 len/k 个片段；其中 前 len%k个片段，长度为 len/k + 1;
        // 实现cut(ListNode* head,int k); 切割前k个节点，返回第k+1个节点后的链表
        // 循环切割，时间复杂度为O(N)
        vector<ListNode*> vec;
        ListNode* cur=root;
        int len=getLen(root);
        if (len<k){
            for(int i=0;i<k;i++){
                vec.push_back(cur);
                cur=cut(cur,1);
            }
        }else{
            int step=len/k;
            int m=len%k;
            int i=0;
            for (i=0;i<m;i++){
                vec.push_back(cur);
                cur=cut(cur,step+1);
            }
            for(i=m;i<k;i++){
                vec.push_back(cur);
                cur=cut(cur,step);
            }
        }
        return vec;
    }
    
    int getLen(ListNode* head){
        if(head==NULL){
            return 0;
        }
        int len=0;
        ListNode* cur=head;
        while(cur){
            cur=cur->next;
            len++;
        }
        return len;
    }
    
    ListNode* cut(ListNode* head,int k){
        while(k>1 && head){
            head=head->next;
            k--;
        }
        if (head==NULL){
            return NULL;
        }
        ListNode* tmp=head->next;
        head->next=NULL;
        return tmp;
    }
};

6.使用额外结构降低时间复杂度

138.复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

题解：先全部复制一遍，再进行指针关联

class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    // hash 空间复杂O(N) 
    // 原地复制 空间复杂O(1) 复制节点 复制random 拆链表
    Node* copyRandomList(Node* head) {
        if(head==nullptr){
            return nullptr;
        }
        map<Node*,Node*> map;
        Node* cur=head;
        while(cur){
            map[cur]=new Node(cur->val,nullptr,nullptr);
            cur=cur->next;
        }
        cur=head;
        while(cur){
            map[cur]->next=map[cur->next];
            map[cur]->random=map[cur->random];
            cur=cur->next;
        }
        return map[head];
    }
};

817.链表组件

给定一个链表（链表结点包含一个整型值）的头结点 head。

同时给定列表 G，该列表是上述链表中整型值的一个子集。

返回列表 G 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 G 中）构成的集合。

示例 1：

输入: 
head: 0->1->2->3
G = [0, 1, 3]
输出: 2
解释: 
链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，同理 [3] 也是一个组件，故返回 2。
示例 2：

输入: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
输出: 2
解释: 
链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& G) {
        set<int> m_set;
        for (int i=0;i<G.size();i++){
            m_set.insert(G[i]);
        }
        ListNode* cur=head;
        int num = 0;
        while(cur){
            if(m_set.find(cur->val)!= m_set.end() && (cur->next==NULL || m_set.find(cur->next->val)== m_set.end())){
                num++;
            }
            cur=cur->next;
        }
        return num;
        
    }
};

1019.链表中下一个更大节点

给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。

每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。

返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。

注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。

示例 1：

输入：[2,1,5]
输出：[5,5,0]
示例 2：

输入：[2,7,4,3,5]
输出：[7,0,5,5,0]
示例 3：

输入：[1,7,5,1,9,2,5,1]
输出：[7,9,9,9,0,5,0,0]

class Solution {
public:
   //题解，使用栈先进后出。找到第一个比较大的就更新对应的数组值。
    vector<int> nextLargerNodes(ListNode* head) {
        int count = 0; //计数，作为下标
        vector<int> result;
        stack<pair<int, int>> tmp; //first为val，second为下标
        while (head)
        {
            result.push_back(0); //给result数组后面+0，1为保证长度，2是默认值（后无更大的值的话）为0
            while (!tmp.empty() &&
                   head->val > tmp.top().first) //栈不为空且head指针的val值大于栈顶的元素的值
            {
                result[tmp.top().second] = head->val; //result数组修改，满足题意要求的最大值，然后出栈，继续循环
                tmp.pop();
            }
            tmp.push(make_pair(head->val, count++)); //count++计数
            head = head->next; //下一个节点
        }
        return result;       
    }
};

7.快慢指针

160.相交链表

编写一个程序，找到两个单链表相交的起始节点。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int aLen=0;
        int bLen=0;
        ListNode *curA=headA;
        ListNode *curB=headB;
        while(curA!=NULL){
            curA=curA->next;
            aLen++;
        }
        while(curB!=NULL){
            curB=curB->next;
            bLen++;
        }
        int i=0;
        curA=headA;
        curB=headB;
        if (aLen>bLen){
            for(i=0;i<aLen-bLen;i++){
                curA=curA->next;
            }
        }else{
            for(i=0;i<bLen-aLen;i++){
                curB=curB->next;
            }   
        }
        while(curA){
            if(curA==curB){
                return curA;
            }else{
                curA=curA->next;
                curB=curB->next;
                i++;
            } 
        }
        return NULL;
    }
};

234.回文链表

请判断一个链表是否为回文链表。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==NULL||head->next==NULL){
            return true;
        }
        ListNode* slow=head;
        ListNode* fast=head->next;
        while(fast!=NULL && fast->next!=NULL){
            fast=fast->next->next;
            slow=slow->next;
        }
        ListNode* r=resver(slow->next);
        while(r!=NULL){
            if(r->val!=head->val){
                return false;
            }
            r=r->next;
            head=head->next;
        }
        return true;
    }
    
    ListNode* resver(ListNode* head){
        if(head==NULL||head->next==NULL){
            return head;
        }
        ListNode* pre=NULL;
        ListNode* cur=head;
        ListNode* next;
        while(cur!=NULL){
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};

328.奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:

输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
说明:

应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head==NULL||head->next==NULL){
            return head;
        }
        ListNode* t1=head;
        ListNode* t2=head->next;
        ListNode* t2head=t2; //必须先保存，才可以保证链接。因为后续head->next 变了。
        while(t2!=NULL && t2->next!=NULL){
            t1->next=t2->next;
            t1=t1->next;
            t2->next=t1->next;
            t2=t2->next;
        }
        t1->next=t2head;
        return head;
    }
};

LeetCode-链表

LeetCode-链表

1.反转链表

206.反转链表。

92.反转链表II

2.删除元素

237.删除链表中的节点

203.移除链表元素

19.删除链表的倒数第N个节点

83.删除排序链表中的重复元素

82.删除排序链表中的重复元素II

1171.从链表中删去总和值为0的连续节点

3.合并链表

21.合并两个有序链表

23.合并K个有序链表

2. 两数相加

445.两数相加II

4.重排链表

24.两两交换链表中的节点

25. k个一组反转链表

61.旋转链表

143.重排链表

147.链表进行插入排序

148.排序链表

5.分隔链表

86.分隔链表

109.有序链表转换二叉搜索树

725.分隔链表

6.使用额外结构降低时间复杂度

138.复制带随机指针的链表

817.链表组件

1019.链表中下一个更大节点

7.快慢指针

160.相交链表

234.回文链表

328.奇偶链表

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读