本文共 16468 字，大约阅读时间需要 54 分钟。

目录

---

链表结构

struct ListNode {    int val;    ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};

 

构建链表——尾插法

ListNode * CreateNode(int n)  {	ListNode *head = NULL, *pnew = NULL, *ptail = NULL; 	int num, i = 1;	while (i <= n)	{		pnew = new ListNode(0);		cout << "输入第" << i << "个结点:" << endl;		cin >> num;		pnew->val = num;		pnew->next = NULL;		if (head == NULL)			head = pnew;		else		{			ptail->next = pnew;		}		ptail = pnew;		i++;	}	pnew = NULL;	delete pnew;	return head;}

 

 

 

leetcode  206 单链表反转——（考察指针）

示例:

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

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

 

思路：

迭代

设置两个指针（new_head和next），new_head始终使其指向新链表的头结点，next始终使其指向待反转链表的头结点。

步骤图示如下（渣绘）

代码如下：

/** * 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==nullptr)||(head->next==nullptr))            return head;                ListNode * new_head=nullptr,*next=nullptr;        while(head){            //next指向待排序链表的头结点            next=head->next;            //令被拆下来的节点的next指针指向新链表的头结点            head->next=new_head;            //移动new_head，使其保持指向新链表的头结点            new_head=head;            //使head指向待排序链表的头结点            head=next;        }        return new_head;    }};

 

递归

递归着将链表层层拆解，等遇到尾节点时，将其设置为链表的头结点，之后层层从递归中返回，将之前记录的节点设置为当前链表的尾节点。类似下图（渣绘，求原谅）：

代码如下：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* helper(ListNode*  head){    ListNode*  current_head=nullptr;    ListNode*  head_next=nullptr;    if ((head == NULL)||(head->next == NULL)){        return head;    }else{        //记下当前的头结点a0        current_head = head;        //记下当前头结点后面的结点a1        head_next = head->next;        //返回(a1...an)逆转后的头结点        head = helper(head_next);        //用上面保存的地址（逆转后的尾结点）指向原来的头结点a0        head_next->next = current_head;        //将a0的next域置零        current_head->next = NULL;    }        //返回a0        return head;}        ListNode* reverseList(ListNode* head) {        if((head==nullptr)||(head->next==nullptr))            return head;                ListNode * tail=nullptr;        tail=helper(head);        return tail;    }};

 

 

leetcode 234  回文链表

请判断一个链表是否为回文链表。你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

示例 1:

输入: 1->2输出: false

示例 2:

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

思路：

空间复杂度为O(1)，因此只能哟经指针了。一个快指针每次走两步，慢指针每次走一步，以此来找到链表的中间节点。

之后对后半段单链表进行逆序。将逆序之后的链表与元链表的前半段进行比较。

/*struct ListNode {    int val;    struct ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};*/class PalindromeList {public:    bool chkPalindrome(ListNode* A) {        ListNode *fast=A, *slow=A;        //找到中间节点        while(fast){            slow=slow->next;            fast=fast->next?fast->next->next:fast->next;        }        //对后半段进行逆序        ListNode *next=nullptr, *newhead=nullptr;        while(slow){            next=slow->next;            slow->next=newhead;            newhead=slow;            slow=next;        }                //比较        while (A && newhead){            if (A->val != newhead->val){                return false;            }            A = A->next;            newhead = newhead->next;        }        return true;    }};

 

 

leetcode 92  链表中间段逆序

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

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

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

 

思路：

关键点在于这四个节点

找到四个节点之后，对需要逆置的段进行单链表逆置操作即可。

特殊条件：m=1的情况。m=1，说明逆置段开始节点的前驱是一个空指针，此时应该返回以逆置段开始节点为作为头结点的链表。

 

实现代码：

/** * 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(head==nullptr) return nullptr;        if(n==1) return head;//只有一个节点，则必返回头结点                ListNode* result=head; //返回的结果        ListNode* pre_head=NULL;//逆置段开始节点的前驱        ListNode* new_head=NULL;        ListNode* tail=head; //逆置段的尾节点                int change_len=n-m+1; //要逆置的节点个数        while(head&&--m){            pre_head=head; //pre_head指向逆置段头结点的前驱            head=head->next;        }                tail=head;//逆置段的尾节点        ListNode* next=nullptr;        //一波单链表逆序操作        while(head && change_len--){            next=head->next;            head->next=new_head;            new_head=head;            head=next;        }                tail->next=head; //逆置段尾节点连接不需要逆置的那段节点        if(pre_head){ //m!=1的情况           pre_head->next=new_head;        }else{            result=new_head;        }        return result;    }};

 

 

leetcode21 合并两个链表

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

示例：

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

思路：

1. 先检查两个链表是否都非空，如果存在空链接，则返回另一个链表的头结点
2. 然后设置一个空指针，使其指向两个链表中头结点值较小的节点，将该指针作为结果链表的头结点
3. 之后进入循环体，不断比较，直到有一方的链表到达了尾节点为止
4. 最后连接剩余的未参与比较的链表段

实现代码：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {        //1        if((!l2)||(!l1)){ //如果存在空链表，则返回另一个链表的头结点            if(l1){                return l1;            }else{                return l2;            }        }                //2        ListNode *result=(l1->val>l2->val)?l2:l1;//结果的头结点        if(result==l1){            l1=l1->next;        }else if(result==l2){            l2=l2->next;        }                //3        ListNode *helper=result;        while(l1&&l2){            if(l1->val>l2->val){                helper->next=l2;                l2=l2->next;            }else{                helper->next=l1;                l1=l1->next;            }            helper=helper->next;        }                //4        //连接l1或l2的剩余节点        if(l1){            helper->next=l1;        }else if(l2){            helper->next=l2;        }                return result;    }};

 

 

 

LeetCode19  删除链表的倒数第 n 个节点

题目：

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

示例：

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

使用两根指针，指针间距离为n-1.当一根指针指向链表尾节点时，证明另一根指针所指节点应该被删除。

/** * 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) {        ListNode* pNode = head;        ListNode* fast = head;        ListNode* slow = head;        //使快指针移动n步，使其与慢指针之间保持一定距离        for (int i = 0; i < n; ++i) fast = fast->next;        if (fast == nullptr)        {            pNode = head->next;            delete head; head = nullptr;            return pNode;        }        //使快慢指针同步运动，直到快指针指向链表尾        while (fast->next != nullptr)        {            fast = fast->next;            slow = slow->next;        }        //使pNext指向该被删除的节点        ListNode* pNext = slow->next;        slow->next = pNext->next;        //释放空间        delete pNext; pNext = nullptr;        return head;    }};

 

 

 

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

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

示例:

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

说明:

• 你的算法只能使用常数的额外空间。
• 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

递归

/** * 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) {        if(head == NULL || head->next == NULL) return head;        ListNode* temp = head -> next;        head -> next = swapPairs(temp -> next);        temp -> next = head;        return temp;    }};

循环

/** * 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) {        ListNode *dummyHead = new ListNode(0);        dummyHead->next = head;        ListNode *p = dummyHead;        while (p->next && p->next->next) {            ListNode *node1 = p->next;            ListNode *node2 = node1->next;            ListNode *next = node2->next;                        node2->next = node1;            node1->next = next;            p->next = node2;            p = node1;        }        ListNode *ret = dummyHead->next;        delete dummyHead;        return ret;    }};

 

 

 

leetcode 160 相交链表

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

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3输出：Reference of the node with value = 8输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1输出：Reference of the node with value = 2输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2输出：null输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。解释：这两个链表不相交，因此返回 null。

注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

原题：

/** * 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) {            }};

思路：

1、使用set——太low

将一个链表中的各个节点的地址存入set中，然后遍历另一个节点。发现地址相同的，就是相交的节点了（存地址，因为不同节点的值可以相同，但是地址不会重复）

class Solution {public:    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {        set
   
    con;        //将链表A中的地址存入set中        while(headA){            con.insert(headA);            headA=headA->next;        }        //遍历链表B的地址，找到地址相同的节点        while(headB){            if(con.find(headB)!=con.end()){                return headB;            }            headB=headB->next;        }        return nullptr;    }};
   

 

2、方法2

static const auto _____ = []() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    return nullptr;}();class Solution {public:    vector
   
     getDistence(ListNode *headA, ListNode *headB){        vector
    
     ans;        int res=0;        ListNode *temp;        //疑问，这里改变的指针指向，会不会影响原函数        while(headA && headB){            headA=headA->next;            headB=headB->next;        }                if(headA!=nullptr){            ans.push_back(1);            temp=headA;        }else if(headB!=nullptr){            ans.push_back(2);            temp=headB;        }else{            ans.push_back(0);            temp=headA;        }              while(temp){            res++;            temp=temp->next;        }        ans.push_back(res);        return ans;    }            ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {        if((!headA)||(!headB)) return nullptr;                //获取哪一个链表长，并获取两个链表长度的差距        vector
     
      res=getDistence(headA, headB);                if(res[0]==1){            while(res[1]--){                headA=headA->next;            }        }else if(res[0]==2){            while(res[1]--){                headB=headB->next;            }        }                while(headA!=headB){            headA=headA->next;            headB=headB->next;        }                return headA;            }};
     
    
   

加了这句之后，代码就快了，。。。

static const auto _____ = []() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    return nullptr;}();

方法三：

双指针遍历两个链表，当链表B遍历到尾部时，使其next指向链表A的表头；同理，当链表A遍历到尾部时，使其next指向链表B的表头。如此遍历，有重合就证明有交点。最多遍历 链表A的长度+链表B的长度 即可判断出是否有相交的节点。

class Solution {    public:        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {            ListNode *pA = headA;            ListNode *pB = headB;            // 有空链表肯定无交点            if(pA == nullptr || pB == nullptr){                return nullptr;            }//if            while(pA && pB){                // 交点                if(pA == pB){                    return pA;                }                if(pA->next && pB->next){                    pA = pA->next;                    pB = pB->next;                }                // 到达pA末尾,pB未到达                else if(!pA->next && pB->next){                    pA = headB;                    pB = pB->next;                }                // 到达pB末尾,pA未到达                else if(pA->next && !pB->next){                    pA = pA->next;                    pB = headA;                }                // 同时到达pA,pB末尾                else{                    return nullptr;                }            }            return nullptr;        }};

 

 

 

leetcode 142 环形链表

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

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

说明：不允许修改给定的链表。

示例 1：

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

示例 2：

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

示例 3：

输入：head = [1], pos = -1输出：no cycle解释：链表中没有环。

进阶：

你是否可以不用额外空间解决此题？ 能！！！

方法一：用set，太low

class Solution {public:    ListNode *detectCycle(ListNode *head) {        if(!head) return nullptr;               set
   
    res;          while(head){            if(res.find(head)!=res.end()){                return head;            }            res.insert(head);            head=head->next;        }        return nullptr;    }};
   

 

方法二：快慢指针

快指针和慢指针，如果链表有环，则两个指针终会相遇。但是像雨点未必是环的入口，如图：

那么环该如何求？由于快指针的速度是慢指针的两倍，且链表有环，则两个指针走过的地方可以分为a, b, c 三块：

static const auto _____ = []() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    return nullptr;}();class Solution {public:    ListNode *detectCycle(ListNode *head) {        if(!head) return nullptr;                ListNode *fast=head;        ListNode *slow=head;        ListNode *meet=nullptr;                while(fast){            slow=slow->next;            fast=fast->next;                        if(!fast) return nullptr;//链表无环            fast=fast->next;                        if(fast==slow){                meet=slow;                break;            }        }                while(head && meet){            if(head==meet){                return head;            }            head=head->next;            meet=meet->next;        }                        return nullptr;                    }};

 

 

 

leetcode 86 分隔链表

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

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

示例:

输入: head = 1->4->3->2->5->2, x = 3输出: 1->2->2->4->3->5

思路：

设置两个临时头结点，分别存储小于x的节点和大于等于x的节点。最后把两段链表连接起来即可。

class Solution {public:    ListNode *partition(ListNode *head, int x) {          //创建两个临时头结点        ListNode *leftHead = (ListNode*)malloc(sizeof(ListNode));          ListNode *rightHead = (ListNode*)malloc(sizeof(ListNode));         //小的都存lpre后面，其余的都存rpre后面。之后把这俩链接就可以了        ListNode *lpre = leftHead,*rpre = rightHead;          while(head != NULL){              if(head->val < x){                  lpre->next = head;                  //使得lpre指向head，新的小点都查到lpre后面                lpre = head;              }              else{                  rpre->next = head;                  rpre = head;              }              head = head->next;          }          rpre->next = NULL;          lpre->next = rightHead->next;          return leftHead->next;      }  };

 

 

 

leetcode 138 复制随机指针的链表

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

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

思路：——通过map映射来实现。

第一步：

拷贝一下原链表

然后将原链表的地址与原链表的编号作为键值对存入一个map中，用一个vector存储另一个链表的各个节点的地址。

第二步：

遍历原链表，查看链表的random指针指向的是哪一个节点的地址，通过地址获取random指针指向的节点编号。然后在另一个vector中去查找对应的地址并构建新链表的random指针。

实现代码：

class Solution {public:    RandomListNode *copyRandomList(RandomListNode *head) {        if(!head) return nullptr;                map
   
    node_map;        vector
    
     node_vec;                RandomListNode *ptr=head;        int i=0; //节点编号        while(ptr){            //创建新链表的节点，并将地址存入vector中            node_vec.push_back(new RandomListNode(ptr->label));            //创建map映射，map有重载 [] ，如果map中没有 [] 中的元素，则会创建键值对并存入map中            //具体实现可以参考源码            node_map[ptr]=i++;            ptr=ptr->next;        }                //结尾是一个空指针，push_back了一个0之后，        node_vec.push_back(0);        ptr=head;        i=0;        int id=0;        while(ptr){            node_vec[i]->next=node_vec[i+1];            if(ptr->random){                id=node_map[ptr->random];                node_vec[i]->random=node_vec[id];                            }            //因为有  node_vec.push_back(0);，否则最后结尾是指针并不指向空，            //导致输出的结果不正确            ptr=ptr->next;            i++;        }                return node_vec[0];            }};