专题二：链表

经典做法：双指针一起走、三指针一起走、加伪头节点

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

题目：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/submissions/

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

1、分析

由于头节点也可能被删除，所以需要加上伪头节点。
采用双指针一起走法，即先用一个指针p走n步，再用另一个指针q从起点出发，两指针同时往后走，当p走到最后一个节点时，停止往后走，这时q的下一个节点即是需要删除的节点。
删除q的下一个节点：q->next=q->next->next

双指针走法，保证了只对链表遍历一遍的时间复杂度O(n)

tip：若希望指针p走到最后一个节点停止，则循环判断的条件是：while(p->naxt)
若希望指针p走到最后一个节点的下一个节点停止，则循环判断的条件是：while(p)

2、代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        auto pre=new ListNode(-1);
        pre->next=head;
        auto p=pre;
        while(n--)  //p先往后走n步
        {
            p=p->next;
        }
        auto q=pre;
        while(p->next)  //p和q同时走
        {
            p=p->next;
            q=q->next;
        }
        q->next=q->next->next;  //删除q的下一个节点
        return pre->next;  //返回头节点
    }
};

LeetCode 237 删除链表中的节点

题目：https://leetcode-cn.com/problems/delete-node-in-a-linked-list/submissions/

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

示例 1:

输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

1、分析

我们可以让下一个节点伪装成我们要删除的当前节点，即先让当前节点的值等于下一个节点的值，此时删除节点即可变成下一个节点，再删除下一个节点即可。

node->val=node->next->val;  //让当前节点的值等于下一个节点的值
node->next=node->next->next;  //删除下一个节点

以上两句可以合并成一句：(*node)=(*node->next)

2、代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        (*node)=(*node->next);
    }
};

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

题目：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

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

示例 1:

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

1、分析

采用双指针法

指针p用来遍历整个链表
指针q每次从p出发，往后遍历重复元素
当重复元素都删除了，p继续往下走，q重复上一步

2、代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        auto p=head;
        while(p)
        {
            auto q=p->next;
            while(q)
            {
                if(q->val==p->val)
                    p->next=q->next;
                else break;
                q=q->next;
            }
            p=p->next;
        }
        return head;
    }
};

LeetCode 61 旋转链表

题目：https://leetcode-cn.com/problems/rotate-list/submissions/

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

示例 1:

输入: 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

1、分析

旋转k步即是把倒数k个节点移到链表前面。首先和LeetCode 19题一样，采用双指针一起走法找到倒数第k个节点的前一个节点位置q，此时p指向最后一个节点，让p指向头，头指向q的下一个节点，q指向NULL.

2、代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL) return head;
        int n=0;
        for(auto p=head;p;p=p->next) n++;  //因为head为NULL时，n=0，所以需要单独考虑
        auto pre=new ListNode(-1);
        pre->next=head;
        k=k%n;         //这是一个循环的操作，循环倍数就是链表的长度，所以先模n
        auto p=pre;
        while(k--)
        {
            p=p->next;
        }
        auto q=pre;
        while(p->next)
        {
            p=p->next;
            q=q->next;
        }
        p->next=pre->next;
        pre->next=q->next;
        q->next=NULL;
        return pre->next;
    }
};

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

题目：https://leetcode-cn.com/problems/swap-nodes-in-pairs/submissions/

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

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

示例:

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

1、分析

采用三指针一起走法，由于头节点可能改变，所以需要创建一个伪头节点

如上图所示，我们需要交换b和c，则先有一个a指向b，1）b->next=c->next；2）c->next=b；3）a->next=c

再一起把abc指针后移，交换3和4

2、代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        auto pre=new ListNode(-1);
        pre->next=head;
        auto a=pre;
        while(a&&a->next&&a->next->next)
        {
            auto b=a->next;
            auto c=b->next;
            b->next=c->next;
            c->next=b;
            a->next=c;
            a=b;
        }
        return pre->next;
    }
};

LeetCode 206 反转链表

题目：https://leetcode-cn.com/problems/reverse-linked-list/

反转一个单链表。

示例:

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

1、分析

采用三指针一起走法，反转链表即是让链表的每个指针反转，由于头节点可能会改变，所以创建一个伪头节点。

如上图所示，反转ab之间的指针方向。

2、代码

/**
 * 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||!head->next) return head;
        auto pre=new ListNode(-1);
        pre->next=head;
        
        auto a=head;
        auto b=a->next;
        while(b)
        {
            auto c=b->next;
            b->next=a;
            a=b;
            b=c;
        }
        pre->next->next=NULL;
        pre->next=a;
        return pre->next;
    }
};

LeetCode 92 反转链表II

题目：https://leetcode-cn.com/problems/reverse-linked-list-ii/

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

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

1、分析

由于头节点可能改变，所以创建一个伪头节点。先记录要反转的第一个节点的前一个节点，记为p。然后反转n-m长度的链表。再把链表重新串起来。

链表反转和上一题思路一样，上图的3和4做法是：p->next->next=b、p->next=a

2、代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(m==n) return head;
        int d=n-m;
        auto pre=new ListNode(-1);
        pre->next=head;
        auto p=pre;
        while(--m)
        {
            p=p->next;
        }
        auto a=p->next;
        auto b=a->next;
        while(d--)
        {
            auto c=b->next;
            b->next=a;
            a=b;
            b=c;
        }
        p->next->next=b;
        p->next=a;
        return pre->next;
    }
};

LeetCode 160 相交链表

题目：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

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

如下面的两个链表：

在节点 c1 开始相交。

1、分析

让两个指针pA、pB分别从A和B同时出发，当走到链表尽头时，再从另一个链表的头开始重新往后走，则一定会在相交点相遇。

2、代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto pA=headA;
        auto pB=headB;
        while(pA!=pB)
        {
            if(!pA) pA=headB;
            else pA=pA->next;
            if(!pB) pB=headA;
            else pB=pB->next;
        }
        return pA;
    }
};

LeetCode 142 环形链表II

题目：https://leetcode-cn.com/problems/linked-list-cycle-ii/submissions/

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

1、分析

如上图所示，我们有一个快慢指针fast、slow，fast每次走两步，slow每次走一步，当slow走到slow1处时，假设fast走到fast1处，此时slow走了x步，fast走了2x步，假设fast1距离slow1还有y步，则此时slow继续走y步，fast继续走2y步，则此时slow和fast在如图slow2和fast2处相遇，再把slow重新放到起点开始，之后fast和slow同时往后每走一步，则一定在slow1处相遇，即为环的交点处。因为之后两个指针要走的距离都是x步。

2、代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head) return head;
        auto fast=head;
        auto slow=head;
        while(fast)
        {
            fast=fast->next;
            slow=slow->next;
            if(fast) 
            {
                fast=fast->next;
                if(fast==slow) //第一次相遇，让slow重回起点
                {
                    slow=head;
                    while(fast!=slow)  //第二次相遇即为环的交点
                    {
                        fast=fast->next;
                        slow=slow->next;
                    }
                    return fast;
                }
            }
        }
        return NULL;
    }
};

LeetCode 148 排序链表

题目：https://leetcode-cn.com/problems/sort-list/

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

示例 1:

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

1、分析

采用自顶向下的归并排序，需要用到递归，而递归需要用到系统栈，递归的深度是logn，所以空间复杂度为O(logn)，不满足常数级空间复杂度，因此采用自低向上的归并排序。先两两排序，再根据排序结果4个一组，用归并排序。

2、代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        auto pre=new ListNode(-1);
        pre->next=head;
        int n=0;
        for(auto p=head;p;p=p->next) n++;
        for(int i=1;i<n;i*=2)  //枚举每一段的长度
        {
            auto begin=pre;
            for(int j=0;j+i<n;j+=i*2) //对每一段进行归并
            {
                auto first=begin->next,second=first;
                for(int k=0;k<i;k++) second=second->next;
                int f=0,s=0;
                while(f<i&&s<i&&second)
                {
                    if(first->val<second->val)
                    {
                        begin=begin->next=first;
                        first=first->next;
                        f++;
                    }
                    else
                    {
                        begin=begin->next=second;
                        second=second->next;
                        s++;
                    }
                }
                while(f<i)
                {
                    begin=begin->next=first;
                    first=first->next;
                    f++;
                }
                while(s<i&&second)
                {
                    begin=begin->next=second;
                    second=second->next;
                    s++;
                }
                begin->next=second;  //把下一段连接起来
            }
        }
        return pre->next;
    }
};

原文链接：https://blog.csdn.net/qq_36417014/article/details/102718559

【LeetCode系列】【链表专题】

目录

专题二：链表

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

1、分析

2、代码

LeetCode 237 删除链表中的节点

1、分析

2、代码

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

1、分析

2、代码

LeetCode 61 旋转链表

1、分析

2、代码

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

1、分析

2、代码

LeetCode 206 反转链表

1、分析

2、代码

LeetCode 92 反转链表II

1、分析

2、代码

LeetCode 160 相交链表

1、分析

2、代码

LeetCode 142 环形链表II

1、分析

2、代码

LeetCode 148 排序链表

1、分析

2、代码

目录

专题二：链表

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

1、分析

2、 代码

LeetCode 237 删除链表中的节点

1、分析

2、代码

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

1、分析

2、代码

LeetCode 61 旋转链表

1、分析

2、代码

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

1、分析

2、代码

LeetCode 206 反转链表

1、分析

2、代码

LeetCode 92 反转链表II

1、分析

2、代码

LeetCode 160 相交链表

1、分析

2、代码

LeetCode 142 环形链表II

1、分析

2、代码

LeetCode 148 排序链表

1、分析

2、代码

2、代码