猿创征文 | 数据结构初步（七）- 链表oj挑战

怠惰的未禾

发布于 2023-04-27 21:34:21

4820

发布于 2023-04-27 21:34:21

文章被收录于专栏：Linux之越战越勇Linux之越战越勇

前言

学习了链表，这不来写几个题巩固巩固怎么行！

1. 移除链表元素

1.1 题目链接

力扣（LeetCode）链接：移除链表元素

1.2 题目要求

给你一个链表的头节点

head

和一个整数

val

，请你删除链表中所有满足

Node.val == val

的节点，并返回新的头节点。示例 1：输入：

head = [1,2,6,3,4,5,6], val = 6

输出：

[1,2,3,4,5]

示例 2：输入：

head = [], val = 1

输出：

[]

示例 3：输入：

head = [7,7,7,7], val = 7

输出：[] 提示：列表中的节点数目在范围

[0, 104]

内

1 <= Node.val <= 50

0 <= val <= 50

1.3 代码框架

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* removeElements(struct ListNode* head, int val){
}

1.4 思路1分析

(1)

删除链表中与

val

相等的节点，可以从头节点开始遍历链表，如果节点储存的值等于

val

就删除该节点，并建立该节点的上一个节点与该节点下一个节点之间的链接；反之就继续遍历链表；直到遍历完链表中所有节点。

(2)

删除链表中的节点（借助结构体指针变量cur记录）有两种情况：情况1：待删除的节点是头结点。这时需要改变头指针的指向，使其指向待删除节点的下一个节点。情况2：待删除节点不是头结点这时需要先得到待删除节点的上一个节点的地址（借助结构体指针变量prev记录），并建立prev节点与待删除节点的下一个节点的链接，最后再删除释放该节点。

时间复杂度

O(n)

空间复杂度

O(1)

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* removeElements(struct ListNode* head, int val){
    //方法1
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;

    while(cur){
    	//相等，就删除释放节点
        if(cur->val == val){
        	//情况1
            if(cur == head){
                head = head->next;
                free(cur);
                cur = head;
            }
            else{
            //情况2
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else{
        //不相等，就继续遍历
            prev = cur;
            cur = cur->next;
        }
    }
}

1.5 思路2分析

(1)

与思路1相似的思路，不同之处在于引入了一个哨兵头节点guard，该哨兵头不存放任何数据，将作为链表的第一个节点，这样就可以不用再考虑遍历链表时节点是否是头节点的问题了。

(2)

一个结构体指针cur 开始指向guard哨兵头的下一个节点，用于遍历链表时的循环停止条件的判断和是否是需要删除的节点；另一个结构体指针prev指向哨兵头guard，用于记录cur的待删除节点的上一个节点。

(3)

遍历链表结束，我们需要返回的节点地址是哨兵头节点的下一个节点的地址，在返回之前别忘了释放申请的哨兵头节点的空间。

时间复杂度

O(n)

空间复杂度

O(1)

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val){
    //方法2，借助哨兵头节点
    struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    //哨兵头节点链接在链表第一个节点之前
    guard->next = head;
    //cur节点遍历链表（不包括哨兵头节点）
    struct ListNode* cur = head;
    struct ListNode* prev = guard;
    
    while(cur){
        if(cur->val == val){
            //建立链接关系，这里不需要关注是否是头结点了
            prev->next = cur->next;
            //释放
            free(cur);
            //更新cur
            cur = prev->next;
        }
        else{
            prev = cur;
            cur = cur->next;
        }
    }
    //链表遍历结束，哨兵头节点的下一个节点就是结果链表的头结点，而申请的哨兵头节点需要释放掉
    head = guard->next;
    free(guard);
    //guard = NULL;
    return head;
}

1.6 思路3分析

(1)

使用一个新的节点头指针newhead作为结果链表的头节点，仍然需要借助结构体指针cur遍历整个链表；借助结构体指针later记录cur节点的下一个节点。应对当cur节点需要删除时，释放掉cur节点后找不到其下一个节点的情况。

(2)

cur从链表头结点开始遍历整个链表；如果节点储存的值等于

val

，就删除cur节点；如果节点储存的值不等于

val

，就把cur节点尾插到新链表末尾。

(3)

每次找到新链表的末尾（尾节点）都需要遍历新链表，这样时间复杂度会较高；应对的方法是救助一个结构体指针变量tail记录新链表的尾节点，这样每次尾插数据时就不需要在遍历新链表了。

(4)

尾插节点需要把尾节点先与带插入节点进行链接，然后更新新链表尾节点指针tail，更新原链表指针cur和next。

时间复杂度

O(n)

空间复杂度

O(1)

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val){
    //方法3,建立一个新节点
    struct ListNode* cur = head;
    struct ListNode* later = NULL;
    struct ListNode* newhead = NULL;
    struct ListNode* tail = NULL;


    while(cur){
        later = cur->next;
        if(cur->val != val){
            if(newhead == NULL){
                newhead = tail = cur;
                cur = later;
            }
            else{
                tail->next = cur;
                tail = cur;
                cur = later;
            }
        }
        else{
            free(cur);
            cur = later;
        }
    }
    if(tail)
        tail->next = NULL;
    return newhead;
}

2. 反转链表

2.1 题目链接

力扣（LeetCode）链接：反转链表

2.2 题目要求

给你单链表的头节点

head

，请你反转链表，并返回反转后的链表。示例 1：输入：

head = [1,2,3,4,5]

输出：

[5,4,3,2,1]

示例 2：输入：

head = [1,2]

输出：

[2,1]

示例 3：输入：

head = []

输出：

[]

提示：链表中节点的数目范围是

[0, 5000]

-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

2.3 代码框架

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverseList(struct ListNode* head){
}

2.4 思路1分析

(1)

依次取原链表每个节点头插如新的空链表中。

(2)

结构体指针cur开始指向原链表的头节点；结构体指针later记录cur的下一个节点；结构体指针newhead记录新的空链表的头节点（开始没有节点时指向空）。

(3)

每一次循环，先找到cur节点的下一个节点later，cur节点内部指针next指向新链表头指针newhead，头指针newhead指向cur节点；最后更新cur节点的上一个节点last为cur。

时间复杂度

O(n)

空间复杂度

O()

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    //取节点然后头插到新链表
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    struct ListNode* later = NULL;
    while(cur){
        later = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = later;
    }
    return newhead;
}

2.5 思路2分析

(1)

从头节点开始，依次使节点内部指针反向。

(2)

结构体指针cur记录当前节点；结构体指针last记录当前节点的上一个节点（初始指向NULL）；结构体指针later记录当前节点的下一个节点。

(3)

对于cur节点，先通过later记录其下一个节点的地址，再改变cur节点内部指针指向，使其指向上一个节点last节点，然后再更新last指针使其指向cur节点，最后更新cur指针，使其指向later节点。

(4)

反转循环结束之后指针cur刚好指向空，指针last就指向了新链表的第一个节点。

时间复杂度

O(n)

空间复杂度

O(1)

代码实现

3. 链表的中间节点

3.1 题目链接

力扣（LeetCode）链接：链表的中间节点

3.2 题目要求

给定一个头结点为

head

的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。示例 1：输入：

[1,2,3,4,5]

输出：此列表中的结点

(序列化形式：

[3,4,5]

) 返回的结点值为

。 (测评系统对该结点序列化表述是

[3,4,5]

)。注意，我们返回了一个

ListNode

类型的对象

ans

，这样：

ans.val = 3, ans.next.val = 4, ans.next.next.val = 5

, 以及

ans.next.next.next = NULL

. 示例 2：输入：

[1,2,3,4,5,6]

输出：此列表中的结点

(序列化形式：

[4,5,6]

) 由于该列表有两个中间结点，值分别为

和

，我们返回第二个结点。提示：给定链表的结点数介于

和

100

之间。

3.3 代码框架

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* middleNode(struct ListNode* head){
}

3.4 思路分析

思路1：寻找链表的中间元素，先遍历一遍链表计算出链表的长度len，那么len/2位置就是中间节点，再次遍历链表即可找到对应中间节点。
思路2：快慢指针：一个指针比另一个指针走得快或一个指针先走另一个指针后走

(1)

借助两个指向节点的指针，一个slow、一个fast；

(2)

然后进行循环，slow指针每次走一步，fast指针每次走两步。

(3)

对于奇数个节点的链表：当fast指针走到最后一个节点位置时，slow指针也走到了中间节点位置；

(4)

对于偶数个节点的链表：当fast指针走到NULL时，slow指针也走到了中间节点的位置。时间复杂度

O(n)

空间复杂度

O(1)

3.5 代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* middleNode(struct ListNode* head){
	//快慢指针一开始都指向头节点
   struct ListNode* slow = head;
   struct ListNode* fast = head;
   //循环遍历链表
   while(fast && fast->next){
       fast = fast->next->next;
       slow = slow->next;
   } 
   return slow;
}

4. 链表中倒数第k个节点

4.1 题目链接

牛客网链接：链表中倒数第k个节点

4.2 题目要求

描述输入一个链表，输出该链表中倒数第

个结点。示例1 输入：

1,[1,2,3,4,5]

返回值：

[5]

4.3 代码框架

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
}

4.4 思路1分析

(1)

找倒数第

个节点，使用快慢指针：指针fast先走

步，然后指针fast和slow一起走，直到fast为空结束。

(2)

这种思路下指针slow所指向的节点相对于fast指向的节点是倒数第

k+1

个，故当，fast指针走到NULL时，slow指针恰好指向倒数第

个节点。

(3)

需要特别注意的是边界与边界周围的情况：比如说 头指针为空：说明不存在该节点，函数直接返回NULL k大于或恰好等于总节点个数：说明不存在该节点，函数直接返回NULL

时间复杂度

O(n)

空间复杂度

O(1)

代码实现

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

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        struct ListNode* slow = pListHead;
        struct ListNode* fast = pListHead;
        //fast指针先走k步
        while(k--){
        	//考虑k可能大于总节点的个数的情况，fast已经为NULL了循环不能再进行
            if(fast == NULL){
                return NULL;
            }
            fast = fast->next;
        }
        
        //一起走，直到fast==NULL
        while(fast){
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

4.5 思路2分析

(1)

找倒数第

个节点，使用快慢指针：指针fast先走

k-1

步，然后指针fast和slow一起走，直到fast为尾节点时结束。

(2)

这种思路下指针slow所指向的节点相对于fast指向的节点正好是倒数第

个，故当fast指针走到尾节点时，slow指针恰好指向倒数第

个节点。

(3)

时间复杂度

O(n)

空间复杂度

O(1)

代码实现

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

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {      
        struct ListNode* slow = pListHead;
        struct ListNode* fast = pListHead;
        //fast指针先走k-1步，故使用--k进行循环控制，也要防止fast为空情况     
        while(--k && fast){
            fast = fast->next;
        }    
        if(fast == NULL){
                return NULL;
            }
        
        //一起走，直到fast->next==NULL
        while(fast->next){
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

5. 链表分割

5.1 题目链接

牛客网链接：链表分割

5.2 题目要求

描述现有一链表的头指针

ListNode* pHead

，给一定值x，编写一段代码将所有小于 x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

5.3 代码框架

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
    }
};

5.4 思路分析

(1)

把小于

的节点尾插到一个新的链表less中，把大于

的节点尾插到另一个新的链表greater中，再把小于

链表的尾节点内部指针指向大于

链表的存放数据的头结点，把大于

链表尾节点内部指针指向NULL；这样先分开原链表在链接两个新链表，less链表头结点地址就是操作完成后的链表头结点地址。

(2)

为了简化问题，两个新的链表less与greater都附加一个哨兵头节点guardLess 、guardGreater，原链表中每个节点都选择一个链表进行尾插。为了减少对链表的遍历，我们再借助两个指针tailLess 、tailgreater记录两个新链表的尾节点地址。

(3)

guardLess的下一个节点就是需要的头结点，返回其地址即可。再返回地址之前，如果哨兵头节点是malloc()申请的，就需要手动释放。

时间复杂度

O(n)

空间复杂度

O(1)

5.5 代码实现

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode* guardLess = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* guardGreater = (struct ListNode*)malloc(sizeof(struct ListNode));
        
        struct ListNode* tailLess = guardLess;
        struct ListNode* tailGreater = guardGreater;
        struct ListNode* cur = pHead;
        //哨兵头节点初始指向NULL
        guardLess->next = NULL;
        guardGreater->next = NULL;
        //遍历原链表
        while(cur){
            //小于x
            if(cur->val < x){
                tailLess->next = cur;
                tailLess = tailLess->next;
            }
            else{
            //大于x
                tailGreater->next = cur;
                tailGreater = tailGreater->next;
            }
            //更新cur
            cur = cur->next;
        }
        //链接两个新链表，less链表的尾节点指针指向greater链表的哨兵头节点的下一个节点
        /*这里因为哨兵头节点的存在，就算less链表没有有效数据节点，
        至少tailLess还指向哨兵头，故tailLess一定不会为NULL*/
        tailLess->next = guardGreater->next;
        //greater链表的尾节点保险起见置空
        tailGreater->next = NULL;
        //pHead保存链接后的新链表的头结点地址
        pHead = guardLess->next;
        //释放动态申请空间
        free(guardLess);
        free(guardGreater);
        
        return pHead;
    }   
};

6. 合并两个有序链表

6.1 题目链接

力扣(leetcode)：合并两个有序链表

6.2 题目要求

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

l1 = [1,2,4], l2 = [1,3,4]

输出：

[1,1,2,3,4,4]

示例 2：输入：

l1 = [], l2 = []

输出：

[]

示例 3：输入：

l1 = [], l2 = [0]

输出：

[0]

提示：两个链表的节点数目范围是

[0, 50]

-100 <= Node.val <= 100

和

均按 非递减顺序 排列

6.3 代码框架

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
}

6.4 思路分析

(1)

合并两个有序链表，申请一个哨兵头节点作为新链表的起始节点，哨兵头节点内部指针初始化为NULL，一个节点指针tail指向合并后链表的尾节点，。

(2)

两个指针：cur1指向第一个链表，cur2指向第二个链表；通过这两个指针分别依次遍历这两个未合并之前的链表。如果如果cur1指向链表节点储存的值小于cur2指向的节点储存的值，就把cur1指向的节点尾插到合并后链表尾节点之后，之后更新cur1和tail分别指向下一个节点；反之则对cur2指向的节点进行上述操作。

(3)

创建一个临时指针变量phead记录合并后链表的地址，该地址是哨兵头节点的下一个节点的地址，并且需要释放申请的空间。

(4)

返回新的头节点地址

时间复杂度

O(n+m)

空间复杂度

O(1)

6.5 代码实现

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
	//哨兵头节点
	struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
	guard->next = NULL;
	//遍历链表借助非头指针副本的指针
	struct ListNode* cur1 = list1;
	struct ListNode* cur2 = list2;
	//指向合并后链表的尾节点
	struct ListNode* tail = guard;
	//遍历两个链表，直到有一个指针为空
	while(cur1 && cur2){
		if(cur1->val < cur2->val){
			tail->next = cur1;
			cur1 = cur1->next;
			tail = tail->next;
		}
		else{
			tail->next = cur2;
			cur2 =cur2->next;
			tail = tail->next;
		}
	}
	//把不为空的剩余节点链接到尾节点之后
	if(cur1){
		tail->next = cur1;
	}
	else{
		tail->next = cur2;
	}
	struct ListNode* phead = guard->next;
	free(guard);
	//guard = NULL;
	return phead;
}

7. 回文链表

7.1 题目链接

牛客网链接：回文链表

7.2 题目要求

给你一个单链表的头节点

head

，请你判断该链表是否为回文链表。如果是，返回

true

；否则，返回

false

。示例 1：输入：

head = [1,2,2,1]

输出：

true

示例 2：输入：

head = [1,2]

输出：

false

提示：链表中节点数目在范围

[1, 105]

内

0 <= Node.val <= 9

7.3 代码框架

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

bool isPalindrome(struct ListNode* head){    
}

7.4 思路1分析

(1)

先找出原链表中的中间节点mid，再逆置中间节点及之后的节点，并用remid指针记录逆置后返回的头节点地址。

(2)

原链表节点指针head与新节点指针remid都不为空时进行依次判断：两个节点储存的值不想的就不是回文数，返回flase；两个节点返回的值相等就更新两个指针分别指向下一个节点，循环结束没有返回false就说明是回文数，返回true。

时间复杂度

O(n)

空间复杂度

O(1)

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

//找中间节点，返回结点地址
struct ListNode* ListSearchMid(struct ListNode* head){
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next){
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

//逆置，返回逆置后的头结点地址
struct ListNode* ListReverse(struct ListNode* head){
    struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    guard->next = NULL;
    struct ListNode* cur = head;
    struct ListNode* later = NULL;


    while(cur){
        later = cur->next;
        cur->next = guard->next;
        guard->next = cur;
        cur = later;
    }
    head = guard->next;
    free(guard);
    //guard = NULL;
    return head;
}

bool isPalindrome(struct ListNode* head){
    //中间节点
    struct ListNode* mid = ListSearchMid(head);
    //逆置后原链表后一半的头节点
    struct ListNode* remid = ListReverse(mid);
    //如果两个头节点储存的值相等就继续循环，更新两个指针指向
    //不相等就直接返回false
    while(head && remid){
        if(head->val != remid->val){
            return false;
        }
        head = head->next;
        remid = remid->next;
    }
    //最后返回true
    return true;
}

7.5 思路2分析

(1)

先拷贝一个新的链表，一个指针copyhead指向拷贝链表第一个节点；对这个拷贝的新链表进行整体逆置，创建变量rehead指向逆置后拷贝链表的第一个结点。

(2)

两个指针：cur1指向原链表、cur2指向逆置后链表；循环依次判断连个链表对应节点储存的数据是否相等，如果全部相等，就是回文数，返回true；如果有一个不相等就不是回文数，返回false。

(3)

最后需要释放拷贝链表所有节点申请的空间。

时间复杂度

O(n)

空间复杂度

O(n)

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* BuyNode(val){
    struct ListNode* newnode = 
            (struct ListNode*)malloc(sizeof(struct ListNode));
    if(!newnode){
        exit(-1);
    }
    newnode->val = val;
    newnode->next = NULL;
    return newnode;
}

//逆置，返回逆置后的头结点地址
struct ListNode* ListReverse(struct ListNode* head){
    struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    guard->next = NULL;
    struct ListNode* cur = head;
    struct ListNode* later = NULL;


    while(cur){
        later = cur->next;
        cur->next = guard->next;
        guard->next = cur;
        cur = later;
    }
    head = guard->next;
    free(guard);
    //guard = NULL;
    return head;
}

bool isPalindrome(struct ListNode* head){
	//空链表直接返回false
    if(!head){
        return false;
    }
    struct ListNode* cur1 = head;
    struct ListNode* copyhead = NULL;
    struct ListNode* copytail = NULL;
    //拷贝原链表到新链表
    while(cur1){
        struct ListNode* newnode = BuyNode(cur1->val);
        if(cur1 == head){
            copytail = copyhead = newnode;
        }
        else{
            copytail->next = newnode;
            copytail = newnode;
        }
        cur1 = cur1->next;
    }
    //比较原链表与拷贝再逆置链表
    struct ListNode* recopyhead = ListReverse(copyhead);
    struct ListNode* cur2 = recopyhead;
    cur1 = head;
    while(cur1 && cur2){
        if(cur1->val != cur2->val){
            return false;
        }
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    //释放拷贝链表
    cur2 = recopyhead;
    struct ListNode* later = NULL;
    while(cur2){
        later = cur2->next;
        free(cur2);
        cur2 = later;
    }
    return true;
}

8. 相交链表

8.1 题目链接

力扣(leetcode)链接：相交链表

8.2 题目要求

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回

null

。图示两个链表在节点 c1 开始相交：题目数据保证整个链式结构中不存在环。注意，函数返回结果后，链表必须保持其原始结构。 示例 1：输入：

intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

输出：

Intersected at '8'

提示：

listA

中节点数目为

$listB 中节点数目为

1 <= m, n <= 3 * 104

1 <= Node.val <= 105

0 <= skipA <= m

0 <= skipB <= n

如果

listA

和

listB

没有交点，

intersectVal

为

如果

listA

和

listB

有交点，

intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

8.3 代码框架

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
}

8.4 思路分析

思路1: 对每一个属于链表A的节点进行判断，如果存在一个链表A的节点与链表B里的任意一个节点相同，就说明两个链表相交，不过时间复杂度过高：

O(n*m)

思路2：

(1)

先分别遍历两个链表，计算两个链表的长度lenA 、lenB。

(2)

长度长的那个链表先走差距步（lenA与lenB差值的绝对值），然后两个链表一起走，这样两个链表会同时遍历完。

(3)

如果存在两个两个链表对应节点的地址相等，就说明两个链表相交；连个链表走到结束也不相等，就说明两个链表不相交。时间复杂度

O(n+m)

空间复杂度

O(1)

8.5 代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    int lenA = 0;
    int lenB = 0;
    //先分别遍历一边两个链表求得对应的长度
    while(curA){
        ++lenA;
        curA = curA->next;
    }
    while(curB){
        ++lenB;
        curB = curB->next;
    }
    curA = headA;
    curB = headB;
    //长的先走差距步
    int gap = abs(lenA - lenB);
    struct ListNode* longList = headA, *shortList = headB;
    if(lenA < lenB){
        longList = headB;
        shortList = headA;
    }
    while(gap--){
        longList = longList->next;
    }
    //一起走，遇到相等节点返回接待你地址，都不相等返回NULL
    while(longList && shortList){
        if(longList == shortList){
            return longList;
        }
        longList = longList->next;
        shortList = shortList->next;
    }
    return NULL;
}

9. 环形链表1

9.1 题目链接

力扣(leetcode)链接：环形链表1

9.2 题目要求

给你一个链表的头节点

head

，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪

指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数

pos

来表示链表尾连接到链表中的位置（索引从

开始）。注意：

pos

不作为参数进行传递。仅仅是为了标识链表的实际情况。如果链表中存在环，则返回

true

。否则，返回

false

。

示例 1：输入：

head = [3,2,0,-4], pos = 1

输出：

true

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：输入：

head = [1,2], pos = 0

输出：

true

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：输入：

head = [1], pos = -1

输出：

false

解释：链表中没有环。提示：链表中节点的数目范围是

[0, 104]

-105 <= Node.val <= 105

pos

为

-1

或者链表中的一个有效索引。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

9.3 代码框架

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    
}

9.4 思路分析

(1)

快慢指针，慢指针slow、快指针fast开始都指向头结点；

(2)

慢指针slow依次走一步，慢指针依次走两步；

(3)

如果有环存在，快指针比慢指针先进入环，当慢指针也恰好进入环时，两个指针的距离虽然不知道，但是由于快指针走的快一步两个指针之间的距离会每次都缩小1，直到缩减到0也就是相遇。

(4)

如果不是环，最终快指针先走到链表尾，两个指针也不可能指向同一个节点（除了开始时的头结点）。看慢指针走的情况

时间复杂度

O(n)

空间复杂度

O(1)

9.5 代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    //快慢指针
    //慢指针slow一次走一步，快指针一次走两步
    //如果存在环，则一定有slow指针与fast指向相同节点
    struct ListNode *slow, *fast;
    slow = fast = head;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
        //这里是节点地址相等，不是节点内部val储存的值相等
        if(slow == fast){
            return true;
        }
    }
    return false;
}

10. 环形链表2

10.1 题目链接

力扣(leetcode)链接：环形链表2

10.2 题目要求

给定一个链表的头节点

head

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

null

。如果链表中有某个节点，可以通过连续跟踪

指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果

pos

是

-1

，则在该链表中没有环。注意：

pos

不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。

示例 1：输入：

head = [3,2,0,-4], pos = 1

输出：返回索引为

的链表节点解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：输入：

head = [1,2], pos = 0

输出：返回索引为

的链表节点解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：输入：

head = [1], pos = -1

输出：返回

null

解释：链表中没有环。提示：链表中节点的数目范围在范围

[0, 104]

内

-105 <= Node.val <= 105

pos

的值为

-1

或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

10.3 代码框架

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    
}

10.4 思路1分析

链表长度就是节点的个数。 前提：慢指针slow每次走一步，快指针fast每次走两步 设第一个节点到入环节点长度为L 设慢指针从恰好入环到快慢指针相遇的长度是X 设环的长度是C 设两指针相遇时快指针走了K整圈， 从起始开始到第一次相遇： 慢指针走的长度

Lenslow：L+X

快指针走的长度

Lenfast

：

L+K*C+X

由前提可以知道一个关系：

2 * Lenslow == Lenfast

即：

2 * (L+X) == L+k*C+X

L == k*C - X;

k==1时，L == C-X

含义是 从头节点到入环节点的长度 与 从快慢指针第一次相遇节点到入环节点的长度 相等看慢指针和头指针走的情况：2L+X 时间复杂度

O(n)

空间复杂度

O(1)

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 //找到快慢指针在环的第一个交点，找到返回其地址，找不到返回NULL
 struct ListNode* ListIntersection(struct ListNode* head){
     struct ListNode *slow, *fast;
     slow = fast = head;
     while(fast && fast->next){
         fast = fast->next->next;
         slow = slow->next;
         if(fast == slow){
             return fast;
         }
     }
     return NULL;
 }
struct ListNode *detectCycle(struct ListNode *head) {
    //快慢指针交点地址
    struct ListNode* IntersectionPoint = ListIntersection(head); 
    struct ListNode* cur = head;
    //一个指针从交点处开始，另一个指针从头节点开始，遍历节点
    //如果交点存在，则cur指针会与IntersectionPoint指针在环开始节点相遇
    while(cur && IntersectionPoint){
        if(cur == IntersectionPoint){
            return IntersectionPoint;
        }
        cur =cur->next;
        IntersectionPoint = IntersectionPoint->next;
    }
    /*
    前提：慢指针slow每次走一步，快指针fast每次走两步
    设第一个节点到入环节点长度为L
    设慢指针从恰好入环到快慢指针相遇的长度是X
    设环的长度是C
    设两指针相遇时快指针走了K整圈，
    从起始开始到第一次相遇：
    慢指针走的长度Lenslow：L+X
    快指针走的长度Lenfast：L+K*C+X
    由前提可以知道一个关系：2 * Lenslow == Lenfast
    即：    2 * (L+X)  == L+k*C+X
            L == k*C - X;
            k==1时，L == C-X
    含义是 从头节点到入环节点的长度 与 从快慢指针第一次相遇节点到入环节点的长度 相等
    */
    return NULL;
}

10.5 思路2分析

(1)

转换为链表相交问题先找到快慢指针相交节点及相交节点的上一个节点，使相交节点上一个节点内部指针指向NULL，这样环就断开了，入环节点就是断开后连个链表的第一个交点。

(2)

断开后的链表，一个从原来的头节点开始；另一个头节点就是已经找出的相交节点。分别遍历两个链表计算长度，长的链表先走差距步

(3)

然后两个链表在一起走，两个链表对应节点的地址第一次相等时就是要找的入环节点；找不到返回NULL

(4)

为了不破坏原链表，最后要把链表修复以下：使相交节点的上一个节点内部指针再次指向相交节点

空间复杂度

O(1)

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 //找到快慢指针在环的第一个交点，找到返回其地址，找不到返回NULL
 struct ListNode* ListIntersection(struct ListNode* head){
     struct ListNode *slow, *fast;
     slow = fast = head;
     while(fast && fast->next){
         fast = fast->next->next;
         slow = slow->next;
         if(fast && fast->next == slow->next){
             return fast;
         }
     }
     return NULL;
 }
struct ListNode *detectCycle(struct ListNode *head) {
    //找 交点 及 交点上一个节点
    struct ListNode* IntersectionPointLast = ListIntersection(head);
    //没有环则不相交，交点的上一个交点不存在，为NULL，需要判断一下
    if(!IntersectionPointLast){
        return NULL;
    }
    struct ListNode* IntersectionPoint = IntersectionPointLast->next;
    IntersectionPointLast->next = NULL;
    //找长度
    int lenA = 0;
    int lenB = 0;
    struct ListNode* curA = head;
    while(curA){
        ++lenA;
        curA = curA->next;
    }
    struct ListNode* curB = IntersectionPoint;
    while(curB){
        ++lenB;
        curB = curB->next;
    }
    //长的先走差距步
    //不知道哪个链表长，就打擂台思想，先假定一个链表长，在判断赋值
    struct ListNode* LongList = head,*ShortList = IntersectionPoint;
    if(lenA < lenB){
        LongList = IntersectionPoint;
        ShortList = head;
    }
    int gap = abs(lenA - lenB);
    while(gap--){
        LongList = LongList->next;
    }
    //一起走，第一个相同的节点就是交点
    while(LongList && ShortList){
        if(LongList == ShortList){
            return LongList;
        }
        LongList = LongList->next;
        ShortList = ShortList->next;
    }
    return NULL;
}

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

11.1 题目链接

力扣(leetcode)链接：复制带随机指针的链表

11.2 题目要求

给你一个长度为

的链表，每个节点包含一个额外增加的随机指针

random

，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。深拷贝应该正好由

个 全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的

指针和

random

指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。例如，如果原链表中有

和

两个节点，其中

X.random --> Y

。那么在复制链表中对应的两个节点

和

，同样有

x.random --> y

。返回复制链表的头节点。用一个由

个节点组成的链表来表示输入/输出中的链表。每个节点用一个

[val, random_index]

表示：

val

：一个表示

Node.val

的整数。

random_index

：随机指针指向的节点索引（范围从

到

n-1

）；如果不指向任何节点，则为

null

。你的代码只接受原链表的头节点

head

作为传入参数。

示例 1：输入：

head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

输出：

[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：

head = [[1,1],[2,1]]

输出：

[[1,1],[2,1]]

示例 3：

输入：

head = [[3,null],[3,0],[3,null]]

输出：

[[3,null],[3,0],[3,null]]

提示：

0 <= n <= 1000

-104 <= Node.val <= 104

Node.random

为

null

或指向链表中的节点。

11.3 代码框架

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
	
}

11.4 思路分析

拷贝链表的random不是直接复制原链表对应节点的random，而是指向拷贝链表内的节点。拷贝链表中的这个被指向的节点是相对于原链表的相对位置，比较麻烦。

思路1：时间复杂度

O(n^2)

先拷贝一个新链表，对于拷贝链表的每一个节点的random，都需要在原链表中寻找对应节点的random，需要找到这个random指向的节点是原链表的第几个位置；然后再把拷贝链表的处于对应位置的节点地址赋值给拷贝链表当前节点内部的random。

思路2：

(1)

不是直接把原链表每个节点复制为一个新链表，而是拷贝的节点分别链接到原节点的之后，最后成为一个新的大链表。

(2)

由于这样的结构即每个拷贝节点都在其原节点之后，于是我们有了这样的思路： 原节点与原节点内部的random指向的节点的相对位置 、 其拷贝节点与原节点内部random指向的节点的下一个节点的相对位置 是 一样的；故把原节点内部random指向的节点的下一个节点的地址赋值给其拷贝节点。遍历链表，每一次都执行上述操作。

(3)

再次遍历链表，使拷贝节点组成新链表，同时恢复原链表节点之间的链接，返回新链表地址。

时间复杂度

O(n)

空间复杂度

O(n)

11.5 思路2代码实现

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur = head;
    struct Node* copy = NULL;
    struct Node* later = NULL;
    //拷贝节点并链接至相应节点的后面
    while(cur){
        //拷贝并赋值
        copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        //链接
        later = cur->next;
        cur->next = copy;
        copy->next = later;
        //更新cur
        cur = later;
    }

    //更新拷贝节点的random
    cur = head;
    while(cur){
        copy = cur->next;
        later = copy->next;

        if(cur->random == NULL){
            copy->random = NULL;
        }
        else{
            copy->random = cur->random->next;
        }
        //更新cur
        cur = later;
    }
    //解链接
    cur = head;
    struct Node* copyHead = NULL;
    struct Node* copyTail = NULL;
    while(cur){
        copy = cur->next;
        later = copy->next;

        if(copyHead == NULL){
            copyHead = copyTail = copy;
        }
        else{
            copyTail->next = copy;
            copyTail = copy;
        }
        //恢复原链接
        cur->next = later;
        //更新cur
        cur = later;       
    }
    return copyHead;

	// //建立深拷贝关系
    // struct Node* cur = head;
    // while(cur){
    //     struct Node* copynode = (struct Node*)malloc(sizeof(struct Node));
    //     copynode->val = cur->val;

    //     copynode->next = cur->next;
    //     cur->next = copynode;
    //     cur = cur->next->next; 
    // }
    // //建立各节点random指针联系
    // cur = head;
    // while(cur){
    //     if(!cur->random){
    //         cur->next->random = NULL;
    //     }
    //     else{
    //         //下一个节点的random  random节点的下一个节点
    //         cur->next->random = cur->random->next;
    //     }
    //     cur = cur->next->next;;
    // }
    // //解拷贝
    // cur = head;
    // struct Node* copyhead = NULL;
    // struct Node* copytail = NULL;
    // while(cur){
    //     if(!copyhead){
    //         copyhead = copytail = cur->next;
    //     }
    //     else{
    //         copytail->next = cur->next;
    //         copytail = cur->next;
    //     }
    //     cur->next = cur->next->next;
    //     cur = cur->next;;
    // }
    // return copyhead;
}