leetcode经典链表相关题目(思路、方法、code)

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 10k | 阅读时长 ≈ 9 分钟

链表是最常用的数据结构之一。

首先是链表的结构定义:

1
2
3
4
5
6
7
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
206.反转链表

给定一个链表头节点，将其反转，并输出新的头节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
		if(head==NULL||head->next==NULL)
            return head;
        else
        {
        ListNode* mid=NULL;
        ListNode* next_node=head->next;
        head->next=NULL;//这一步很重要，防止链表循环
        while(next_node!=NULL){
            mid=next_node;
            next_node=next_node->next;
            mid->next=head;
            head=mid;
        }
        return head;
       }
    }      
};

时间复杂度为O(n), 空间复杂度O(1)

递归法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
	{
        #如果为NULL或单节点则返回自身
		if(head==NULL||head->next==NULL) return head;
		else
		{
			ListNode* newhead=NULL;
			newhead=reverseList(head->next); //这意味这已经将除了head之后节点的已经反转
			head->next->next=head;  //故需要令让head->next的next指向head实现head的反转
			head->next=NULL;   //防止链表循环，将head的next置空
			//每层递归都要返回最后一个节点
            return newhead; 		
		}  
    }
};
92. 反转链表 II

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

说明：1$\le$m$\le$n$\le$链表长度

1
2
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
160. 相交链表

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

160_statement

解题思路：

从图中我们可以发现，在相交之后的链表长度是相同的，所以我们从头开始遍历知道两个链表长度相同时再逐个进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA=0,lenB=0;
        if (headA==NULL||headB==NULL)
        	return NULL;
        ListNode* node=headA;
        while(node!=NULL){
        node=node->next;
        lenA++;
        }
        node=headB;
        while(node!=NULL){
        node=node->next;
        lenB++;
        }
        
        int len=lenA-lenB;
        if(lenA<lenB){
        node=headA;
        headA=headB;
        headB=node;
        len*=-1;
        }
        while(len>0){
        headA=headA->next;
        len--;
        }
        while(headA!=NULL){
        	if(headA==headB)
        		return headA;
        	headA=headA->next;
        	headB=headB->next;
        
        }
        
        return NULL;
    }
};

时间复杂度为O(n)，空间复杂度为O(1)。

141. 环形链表

这类链表题目一般都是使用双指针法解决的，例如寻找距离尾部第K个节点、寻找环入口、寻找公共尾部入口等。

给定一个链表，判断链表中是否有环。

第一种结果： fast 指针走过链表末端，说明链表无环，直接返回 null；

TIPS: 若有环，两指针一定会相遇。因为每走 11 轮，fast 与 slow 的间距 +1+1，fast 终会追上 slow；

环形链表

思路：使用快慢指针：快指针每次遍历两个节点，慢指针每次遍历一个节点，没有换很快回NULL，有的话两个指针将会相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL||head->next==NULL)
            return false;
        ListNode* quick=head;
        ListNode* slow=head;
        while(quick!=NULL){
            if(quick->next!=NULL&&quick->next->next!=NULL)
                quick=quick->next->next;
            else
                quick=NULL;
            slow=slow->next;
            if(quick==slow)
                return true;
        }
        return false;
    }
};
//附上一年前的代码
bool hasCycle(struct ListNode *head) {
    struct ListNode *fast=head, *slow=head;
    while( slow && fast && fast->next ){
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow) return true;
    }
    return false;
}
142. 环形链表 II

在141基础上进行改进，给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

方法1：使用SET或者哈希映射

对于每个节点，将其地址通过哈希映射或者直接存入到SET中，然后依次遍历链表，检测新节点是否已经在SET中或者已经被哈希映射。如果遍历结束，则说明没用环。如果遍历过程中发现该地址已经出现在哈希映射表或者SET中，则说明已经遍历过该节点，说明存在环，且该节点为入环节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
	{
        set<ListNode *> node_set; //用set存的是ListNode *
		while(head)
		{
			if(node_set.find(head)!=node_set.end()) //说明之前已经出现
			{
				return head;	
			}
			node_set.insert(head); //将其加入set，继续遍历
			head=head->next;	
		}
		return NULL; 
    }
};

上面的做法时间和空间效率都不高。

方法2：快慢指针法：

具体解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
	{
        ListNode* fast=head,*slow=head;
        while(1){
            if (fast==NULL||fast->next==NULL)
                return NULL;
            fast=fast->next->next;
            slow=slow->next;
            if (fast==slow)
                break;}
            fast=head;
            while(fast!=slow)
            fast=fast->next,slow=slow->next;
            return fast;
            
        
        return NULL;
    }
};
86. 分隔链表

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

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

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

分析：可以设置两个辅助头结点，一个用来存储小于x的节点的链接，一个用来存储大于等于x的节点的链接。因此在此基础上遍历该链表，如果当前节点的之小于x，则将其加入到小于x的链表列，否则加入到大于等于x的链表列。最终，将两个链表合并即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
	{
        if(head==NULL||head->next==NULL) return head;
        
        ListNode a(0),b(0);
        ListNode* less_head=&a;
        ListNode* more_head=&b;
        while(head)  //遍历链表，将每一项加入到对应的链表列
        {
        	if(head->val<x)
        	{
        		less_head->next=head;
        		less_head=less_head->next;
			}
			else
			{
				more_head->next=head;
				more_head=more_head->next;
			}
			head=head->next;
		}
        //将两个链表列进行合并
		more_head->next=NULL;  
		less_head->next=b.next;//令小于链表的尾指向more.next即可
		return a.next;		//返回尾小于链表的next即可
    }
};
83. 删除排序链表中的重复元素

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

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

输入: 1->1->2->3->3
输出: 1->2->3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==NULL||head->next==NULL)
        	return head;
        ListNode*pre =head;
        ListNode*next=head->next;
        while(next!=NULL){
        	if(pre->val==next->val){
        		next=next->next;
        		pre->next=next;//去掉重复的节点
        	}
            else{
                next=next->next;
                pre=pre->next;
            }
        }
        return head;
    }
};
82. 删除排序链表中的重复元素 II（递归）

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。在原来的基础上，只要重复出现了的元素全部删除。

头节点有重复的话将会比较麻烦，这里采用递归的思想：

每次对第一个节点进行检测，如果非重复，则将其加入，对后面继续执行。如果重复，则向后遍历直至与其不一致，执行遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
ListNode* deleteDuplication(ListNode *pHead) {
        if (pHead==NULL || pHead->next==NULL) {
            return pHead;
        }

        if (pHead->val==pHead->next->val) { // 当前节点是重复节点
            ListNode *node = pHead->next;
            while (node != NULL && node->val == pHead->val) {
                // 向后遍历直至与其不一致
                node = node->next;
            }
            return deleteDuplication(node); // 从第一个与当前结点不同的结点继续递归
        } else {
            pHead->next = deleteDuplication(pHead->next); // 从下一个节点继续递归
            return pHead;//保留当前节点
        }

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

思路1：删除倒数第n个，即正数第L-n-1个，我们用一个哑节点作为辅助从而简化情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {    
ListNode dummy=ListNode(0);
dummy.next=head;
int lenth=0;
ListNode first=head;
while(first!=NULL){
    lenth++;
    first=first.next;
}
lenth-=n;
first=dummy;
while(lenth>0){
    lenth--;
    first=first.next;
}
first.next=first.next.next;
return dummy.next;
}};

思路二：通过一次遍历完成

上述算法可以优化为只使用一次遍历。我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n+1 步，而第二个指针将从列表的开头出发。现在，这两个指针被 n 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 nn 个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) { 
	ListNode dummy=ListNode(0);
    dummy.next=head;
    ListNode fir=dummy;
    ListNode sec=dummy;
    for(int i=0;i<=n;i++)
        fir=fir.next;
    while(first!=NULL){
        fir=fir.next;
        sec=sec.next;
    }
    sec.next=sec.next.next;
    return dummy.next;
}}；

结果要好一点点。

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

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

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

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

2. 两数相加

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

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

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

1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
{
	    ListNode *head=new ListNode(0);   //head是结果
		ListNode *p=l1,*q=l2,*cur=head; 
		int carry=0;//作为进位 
		int x=0,y=0;
		while(p!=NULL||q!=NULL) //如果其中一个为0，则将其后面节点均视为0即可 
		{
			x=(p==NULL)?0:(p->val);
            y=(q==NULL)?0:(q->val);
			int sum=x+y+carry; //加起来
			carry=sum/10; //如果小于10则为0,否则为1 
			cur->next=new ListNode(sum%10);
			cur=cur->next;
			if(p!=NULL) p=p->next;
			if(q!=NULL) q=q->next; 
		} 
		if(carry>0) //说明虽然相加完了,但是还是有进位
			cur->next=new ListNode(1);
		return head->next; 
}
};
148. 排序链表

如题，将链表排序。

通过快慢指针找到中点，然后用归并排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == NULL || head->next == NULL) //链表为空或者单节点 
		  return head;
        ListNode* pmid;
        ListNode* slow = head;  //慢指针 
        ListNode* fast = head;  //快指针 
        while (fast && fast->next)
        {
            pmid = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pmid->next = NULL;
	
        return Merge(sortList(head), sortList(slow));
    }

    ListNode* Merge(ListNode* l1, ListNode* l2)  //将两个有序链表合并 
	{
        ListNode dummy(0);  //作为一个哑结点 
        ListNode *p = &dummy;
        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                p->next = l1;
                l1 = l1->next;
            }
            else
            {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        p->next = (l1 == NULL)? l2 : l1;
        return dummy.next;  //返回哑结点下一个节点 
    }
};
-------------本文结束有空来玩-------------
坚持原创技术分享，您的支持将鼓励我继续创作！