链表

1. 删除链表的节点

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

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

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

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

说明:
链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。
实现思路
这道题的题意和“从链表中删除节点”不同,这道题的输入只有待删除节点的引用,然后让你从链表中删除节点,所以采用的思路也有点儿不同。一般从链表中删除节点的思路是将上一个节点的next引用指向待删除节点的下一个节点,如下图所示:

但是现在我们无法获得待删除节点的上一个节点的引用,因此不能采用这种方式。我们采用的方法是这样的:将待删除节点的值赋值为下一个节点的值,然后将待删除节点的引用指向待删除节点的下下个节点,如下图所示:



2. 删除链表的倒数第N个节点

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

1
2
3
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

代码实现

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
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if n == 0:
pass

temp = []
ptr = head
while ptr is not None:
temp.append(ptr)
ptr = ptr.next

m = len(temp)
if n == m: # 判断是不是头节点
head = head.next
return head
else:
temp[m - n - 1].next = temp[m - n].next
return head

class Solution:
def removeNthFromEnd(self, head: 'ListNode', n: 'int') -> 'ListNode':
h = ListNode(0)
h.next = head
before_node, back_node = h, h

for _ in range(n + 1):
before_node = before_node.next

while before_node != None:
before_node = before_node.next
back_node = back_node.next

back_node.next = back_node.next.next
return h.next

3. 反转链表

反转一个单链表

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

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

实现思路
我们知道迭代是从前到后依次处理,直到循环到链尾;而递归恰恰相反,首先一直迭代到尾链也就是递归的判断准则,而后再逐层返回处理到开头(这实际上一种栈结构)。总的来说就是链表翻转操作的顺序对于迭代来说就是从链头到链尾,而递归则是从链尾到链头

  1. 迭代方式
    下图给定一个存放5个数的链表:
    首先对链表设置两个指针,然后依次将旧链表的上的每一项添加到新的链表后面,然后新的链表的头指针移向新的链表头。



代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def reverseList(self, head: ListNode) -> ListNode:

if head is None or head.next is None:
return head

new_head, ptr = head, head.next
head.next = None
while ptr is not None:
temp = ptr.next # 临时存放ptr的下一个节点
ptr.next = new_head # 将ptr的next指向new_head
new_head = ptr # 将new_head后移
ptr = temp # 将下一个节点赋值给ptr
head = new_head
return head
  1. 递归方式
    我们再来看看递归实现链表翻转的实现,前面非递归方式是从前面数1开始往后依次处理,而递归方式则恰恰相反,它先循环找到最后面指向的数5,然后从5开始处理依次翻转整个链表。
      首先指针H迭代到底如下图所示,并且设置一个新的指针作为翻转后的链表的头。由于整个链表翻转之后的头就是最后一个数,所以整个过程NewH指针一直指向存放5的地址空间。

然后H指针逐层返回的时候依次做下图的处理,将H指向的地址赋值给H->next->next指针,并且一定要记得让H->next =NULL,也就是断开现在指针的链接,否则新的链表形成了环,下一层H->next->next赋值的时候会覆盖后续的值。

继续返回操作

上图第一次如果没有将存放4空间的next指针赋值指向NULL,第二次H->next->next=H,就会将存放5的地址空间覆盖为3,这样链表一切都大乱了。接着逐层返回下去,直到对存放1的地址空间处理。

返回到头:

代码实现

1
2
3
4
5
6
7
8
9
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head

h = self.reverseList(head.next)
head.next.next = head
head.next = None
return h

4. 合并两个有序链表

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

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

实现思路

  • 设第一个ListNode为l1,那么之后的就是l1.next,l1.next.next……
  • 设第二个ListNode为l2,那么之后的就是l2.next,l2.next.next……
  • 设置第三个ListNode为l0,作为我们最后需要返回的ListNode对象。
  • 先比较l1.val和l2.val,如果l1.val<l2.val,那么在新链表中,l1肯定是在l2前,所以此时lo=l1,反之l0=l2.
  • 接下来寻找l0.next,如果已经得知l1.val<v2.val,那么 就需要l1.next和l2进行比较;反之如果l1.val>v2.val,那么就需要l1和l2.next进行比较了
    如此递归下去知道最后没有了,递归结束

代码实现

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
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
pre_v = pre_head = ListNode( 0 )
while l1 and l2:#第一个节点
if l1.val <= l2.val:
pre_head.next = l1
l1 = l1.next
else:
pre_head.next = l2
l2 = l2.next
pre_head = pre_head.next
pre_head.next = l1 if l1 is not None else l2#用于添加最后的元素
return pre_v.next

class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:

if l1 is None:
return l2
if l2 is None:
return l1

head = None
if l1.val <= l2.val:
head = l1
head.next = self.mergeTwoLists(l1.next, l2)
else:
head = l2
head.next = self.mergeTwoLists(l1, l2.next)

return head

5. 回文链表

请判断一个链表是不是回文链表

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

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

进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

代码实现

  1. O(n)时间复杂度, O(n)的空间复杂度
1
2
3
4
5
6
7
8
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
temp = []
ptr = head
while ptr is not None:
temp.append(ptr.val)
ptr = ptr.next
return temp == temp[::-1]
  1. O(n)时间复杂度,O(1)的空间复杂度

实现思路
快慢指针:建立两个空字符串,一个存放遍历时的原始字符串,一个存放反转字符串,然后进行比较两个字符串即可。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def isPalindrome(self, head):
if head is None or head.next is None:
return True

str_original, str_reverse = '', ''
while head:
str_original = str_original + str(head.val)
str_reverse = str(head.val) + str_reverse
head = head.next
return str_original == str_reverse

6. 环形链表

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

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

1
2
3
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

1
2
3
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

1
2
3
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

实现思路

如上图所示,如果链表中存在环,那么这个链表一定从某个节点开始就会出现环的入口,最后,遍历经过一圈之后还会回到入口处,题目要求检查是否存在环,那么最简单直接的就是检查遍历链表的过程中是否出现某个节点被遍历的两次。上图中从节点3进入经过4,5,6,7,8 后仍然会回到节点 3,那么这个时候节点 3 就被遍历的两次。

方法1:Hashset
使用一个指针遍历链表,每次访问一个节点首先判断节点是否存在Hash表中,如果存在则存在环,否则将继续添加和遍历,直到遍历结束,证明不存在环。

方法2:快慢指针
快慢指针在链表中的操作比较常见,应该作为一种常用的思路记住,下图中,设置两个指针从head开始遍历,规定两个指针的速度不一样,分别为快慢指针,如图所示,slow 指针每次前进一个节点,fast 指针每次前进两个节点。

因为fast指针每次前进两个,一定比slow指针先到达环的入口处。而当slow指针进入环的时候,fast指针已经经过了两个节点,如下图所示。这个时候,我们将这个过程想象成400m跑步的追及问题。如果存在环的话,因为fast指针速度更快,一定会追上slow指针。而如果fast指针没有追上slow指针,一定是因为链表不存在环。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head is None or head.next is None:
return False

slow, fast = head, head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if fast == slow:
return True
return False