Leetcode：链表刷题（7道经典题目）_关于链表的编程题

Leetcode：链表刷题（7道经典题目）

---

---

---

本文带来的是以链表为主题的一些经典题目：

• 203. 移除链表元素
• 707. 设计链表
• 206. 反转链表
• 24. 两两交换链表中的节点
• 19. 删除链表的倒数第 N 个结点
• 面试题 02.07. 链表相交
• 142. 环形链表 II

---

---

---

链表是一种通过指针串联在一起的线性结构，每一个节点是又两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向NULL（空指针）。链接的入口点称为列表的头结点也就是head。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

• 单链表中的节点只能指向节点的下一个节点。
• 双链表 既可以向前查询也可以向后查询。
• 循环链表，链表首尾相连。循环链表可以用来解决约瑟夫环问题。

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。链表是通过指针域的指针链接在内存中各个节点。所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。

链表Python定义方式：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
1
2
3
4

C++链表定义方式：

// 单链表
struct ListNode {
	int val;  // 节点上存储的元素
	ListNode* next; // 指向下一个节点的指针
	ListNode(int x) : val(x), next(NULL) {}; // 节点的构造函数
};
1
2
3
4
5
6

根据列表生成链表，并返回头节点：

def initList(data):
    if len(data) == 0:
        return
    else:
        head = ListNode(data[0])
        r = head  # 头节点
        p = head  # 指针
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r
1
2
3
4
5
6
7
8
9
10
11
12

CPP：根据列表生成链表，这是用来在本地段测试链表有关题目效果的，方便调试。

// 根据列表生成链表，并返回头节点：
ListNode* initList(vector<int>& data) {
	if (data.size() == 0) {
		return nullptr;
	}
	ListNode* head = new ListNode(data[0]);
	ListNode* cur = head;
	for (int i = 1; i < data.size(); i++) {
		ListNode* node = new ListNode(data[i]);
		cur->next = node;
		cur = cur->next;
	}

	return head;
}

// 根据链表生成数组，并返回数组
vector<int> toVector(ListNode* head) {
	ListNode* cur = head;
	vector<int> num;
	if (head == nullptr) {
		return {};
	}
	while (true) {
		num.push_back(cur->val);
		if (cur->next == nullptr) break;
		cur = cur->next;
	}
	return num;
}
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

链表操作中，可以使用原链表来直接进行删除操作，也可以设置一个虚拟头结点在进行删除操作。

在C，C++中，不要忘了还要从内存中删除这两个移除的节点，如果使用java ，python的话就不用手动管理内存了。

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

由于链表的头节点 head 有可能需要被删除，因此创建哑节点 dummyHead，令 dummyHead.next=head.

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy_head = ListNode(next=head)
        cur = dummy_head
        while cur.next is not None:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy_head.next
1
2
3
4
5
6
7
8
9
10

C++代码如下：

class Solution {
public:
	// 设置一个虚拟头结点在进行移除节点操作
	ListNode* removeElements(ListNode* head, int val) {
		ListNode* dummyHead = new ListNode();
		dummyHead->next = head;
		ListNode* cur = dummyHead;
		while (cur->next != nullptr) {
			if (cur->next->val == val) {
				ListNode* tmp = cur->next;
				cur->next = cur->next->next;
				delete tmp;
			}
			else {
				cur = cur->next;
			}
		}
		head = dummyHead->next;
		delete dummyHead;
		return head;
	}

	// 直接使用原来的链表来进行移除节点操作
	ListNode* removeElements2(ListNode* head, int val) {
		// 删除头节点
		while (head != nullptr && head->val == val) {   // 这里不是 if
			ListNode* tmp = head;
			head = head->next;
			delete tmp;
		}

		ListNode* cur = head;
		while (cur != nullptr && cur->next != nullptr) {
			if (cur->next->val == val) {
				ListNode* tmp = cur->next;
				cur->next = cur->next->next;
				delete tmp;
			}
			else {
				cur = cur->next;
			}
		}
		return head;
	}
};
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
42
43
44
45

707. 设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

单链表：

struct LinkedNode
{
	int val;
	LinkedNode* next;
	LinkedNode() :val(0), next(nullptr) {}
	LinkedNode(int x) :val(x), next(nullptr) {}
	LinkedNode(int x, LinkedNode* next) :val(x), next(next) {}
};


class MyLinkedList {
public:
	MyLinkedList() {
		_dummyHead = new LinkedNode();
		_size = 0;
	}

	int get(int index) {
		if (index<0 || index >= _size) {
			return -1;
		}
		LinkedNode* cur = _dummyHead->next;
		while (index--) {
			cur = cur->next;
		}
		return cur->val;
	}

	void addAtHead(int val) {
		LinkedNode* node = new LinkedNode(val);
		node->next = _dummyHead->next;
		_dummyHead->next = node;
		_size++;
	}

	void addAtTail(int val) {
		LinkedNode* newNode = new LinkedNode(val);
		LinkedNode* cur = _dummyHead;
		while (cur->next != nullptr) {
			cur = cur->next;
		}
		cur->next = newNode;
		_size++;
	}

	void addAtIndex(int index, int val) {
		if (index > _size) return;
		LinkedNode* cur = _dummyHead;
		while (index--) {
			cur = cur->next;
		}
		LinkedNode* newNode = new LinkedNode(val);
		newNode->next = cur->next;
		cur->next = newNode;
		_size++;
	}

	void deleteAtIndex(int index) {
		if (index < 0 || index >= _size) {
			return;
		}
		LinkedNode* cur = _dummyHead;
		while (index--) {
			cur = cur->next;
		}
		LinkedNode* node = cur->next;
		cur->next = cur->next->next;
		delete node;
		_size--;
	}

private:
	LinkedNode* _dummyHead;
	int _size;
};
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

双链表比单链表快得多，测试用例花费的时间比单链表快了两倍。但是它更加复杂，它包含了 size，记录链表元素个数，和伪头伪尾。

struct LinkedNode
{
	int val;
	LinkedNode* next;
	LinkedNode* prev;
	LinkedNode() :val(0), next(nullptr), prev(nullptr) {}
	LinkedNode(int x) :val(x), next(nullptr), prev(nullptr) {}
	LinkedNode(int x, LinkedNode* next) :val(x), next(next), prev(nullptr) {}
	LinkedNode(int x, LinkedNode* next, LinkedNode* prev) :val(x), next(next), prev(prev) {}
};


class MyLinkedList {
public:
	MyLinkedList() {
		m_size = 0;
		head = new LinkedNode();
		tail = new LinkedNode();
		head->next = tail;
		tail->prev = head;
	}

	int get(int index) {
		if (index < 0 || index >= m_size) {
			return -1;
		}
		LinkedNode* cur = head;
		for (int i = 0; i < index; i++) {
			cur = cur->next;
		}
		return cur->next->val;
	}

	void addAtHead(int val) {
		LinkedNode* newNode = new LinkedNode(val, head->next, head);
		newNode->next->prev = newNode;
		newNode->prev->next = newNode;
		m_size++;
	}

	void addAtTail(int val) {
		LinkedNode* newNode = new LinkedNode(val, tail ,tail->prev);
		newNode->prev->next = newNode;
		newNode->next->prev = newNode;
		m_size++;
	}

	void addAtIndex(int index, int val) {
		if (index < 0 || index >m_size) {
			return;
		}
		LinkedNode* cur = head;
		for (int i = 0; i < index; i++) {
			cur = cur->next;
		}
		LinkedNode* newNode = new LinkedNode(val, cur->next, cur);
		newNode->prev->next = newNode;
		newNode->next->prev = newNode;
		m_size++;
	}

	void deleteAtIndex(int index) {
		if (index < 0 || index >= m_size) {
			return;
		}
		LinkedNode* cur = head;
		for (int i = 0; i < index; i++) {
			cur = cur->next;
		}
		LinkedNode* tmp = cur->next;
		cur->next = tmp->next;
		tmp->next->prev = cur;
		delete tmp;
		m_size--;
	}

private:
	int m_size;
	LinkedNode* head;
	LinkedNode* tail;
};
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

class Solution {
public:
	ListNode* reverseList1(ListNode* head) {
		ListNode* cur = head;
		ListNode* prev = nullptr;
		ListNode* tmp = nullptr;
		while (cur != nullptr) {
			tmp = cur->next;
			cur->next = prev;
			prev = cur;
			cur = tmp;
		}
		return prev;
	}
    
    //  递归
	ListNode* reverseList(ListNode* head) {
		return reverse(nullptr, head);
	}
	ListNode* reverse(ListNode* pre, ListNode* cur) {
		if (cur == nullptr) {
			return pre;
		}
		ListNode* tmp = cur->next;
		cur->next = pre;
		return reverse(cur, tmp);
	}
};
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

class Solution {
public:
    //  迭代方法：（双指针）
	ListNode* reverseList1(ListNode* head) {
		ListNode* cur = head;
		ListNode* prev = nullptr;
		ListNode* tmp = nullptr;
		while (cur != nullptr) {
			tmp = cur->next;
			cur->next = prev;
			prev = cur;
			cur = tmp;
		}
		return prev;
	}

	// 递归  从后往前翻转指针指向
	ListNode* reverseList2(ListNode* head) {
		if (head == nullptr) return nullptr;
		if (head->next == nullptr) return head;

		ListNode* last = reverseList2(head->next); // 递归调用，翻转第二个节点开始往后的链表
		head->next->next = head; // 翻转头节点与第二个节点的指向
		head->next = nullptr; // 此时的 head 节点为尾节点，next 需要指向 NULL
		return last;
	}

    
	// 递归  和双指针法是一样的逻辑
	ListNode* reverse(ListNode* pre, ListNode* cur) {
		if (cur == nullptr) return pre;
		ListNode* tmp = cur->next;
		cur->next = pre;
		return reverse(cur, tmp);
	}

	ListNode* reverseList(ListNode* head) {
		return reverse(nullptr, head);
	}
};
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

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

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

初始时，cur指向虚拟头结点，然后进行如下三步：

class Solution {
public:
	ListNode* swapPairs(ListNode* head) {
		ListNode* dummyHead = new ListNode(0, head);
		ListNode* prev = dummyHead;
		while (prev->next != nullptr && prev->next->next != nullptr) {
			ListNode* cur = prev->next;
			ListNode* tmp = cur->next;

			prev->next = tmp;
			cur->next = tmp->next;
			tmp->next = cur;
			
			prev = cur;
		}
		return dummyHead->next;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。进阶：你能尝试使用一趟扫描实现吗？

双指针：快指针比慢指针先走 n 步。

class Solution {
public:
	// 双指针
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		ListNode* dummyHead = new ListNode(0, head);
		ListNode* slow = dummyHead;
		ListNode* fast = dummyHead;

		for (int i = 0; i < n; i++) {
			fast = fast->next;
		}
		while (fast->next != nullptr) {  // 找到节点
			slow = slow->next;
			fast = fast->next;
		}  // 使slow指向前一个节点
    
		ListNode* tmp = slow->next;
		slow->next = slow->next->next;
		delete tmp;

		return dummyHead->next;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

面试题 02.07. 链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。

双指针

class Solution {
public:
    // a+c+b(走对方的路)和b+c+a(走对方的路)，如果相交，两人走的是路长是一致的，会同时达到点。
	ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
		ListNode* curA = headA;
		ListNode* curB = headB;

		while (curA != curB) {  // 要么相遇即节点相等，要么都为空
			curA = (curA != nullptr) ? curA->next : headB;
			curB = (curB != nullptr) ? curB->next : headA;
		}
		return curA;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。

主要考察两知识点：1. 判断链表是否环 2. 如果有环，如何找到这个环的入口.

• 判断链表是否有环:
  • 可以使用快慢指针法， 分别定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
    • fast指针一定先进入环中，如果fast 指针和slow指针相遇的话，一定是在环中相遇
    • fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。
• 如果有环，如何找到这个环的入口：
  • 假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：
    
  • 相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针，（y+z）为 一圈内节点的个数A。
  • 从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast, slow = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                p = head
                q = slow
                while p != q:
                    p = p.next
                    q = q.next
                return p
        return None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

PS

以上题解大多来自【代码随想录】，在此基础上做了一定总结，并附带一些自己的理解。

随缘更新，有错误请指出！

END