处理链表的技巧与习题

单链表操作问题

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

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

示例:

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

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

给定的 n 保证是有效的。

对于这种需要求倒数节点的题,一般下面几个思路,当然比较有名的是快慢指针的做法:

  • 先求取链表的总长L,我们首先从头节点开始对链表进行一次遍历,得到链表的长度L。随后我们再从头节点开始对链表进行一次遍历,当遍历到第 L−n+1 个节点时,它就是我们需要删除的节点。
  • 使用栈,我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则,我们弹出栈的第n个节点就是需要删除的节点,并且目前栈顶的节点就是待删除节点的前驱节点。这样一来,删除操作就变得十分方便了。
  • 快慢指针(先挪动快指针,使得两个节点相距n,之后同时挪动两个指针,直到快指针指到末尾)

所以得到倒数第n个节点的代码如下:

1
2
3
4
5
6
7
8
9
10
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
if not head or k == 0: return None
former, latter = head, head
for _ in range(k):
if not former: return
former = former.next
while former:
former, latter = former.next, latter.next
return latter

使用dummy指针方便删除的操作。因为我们删除倒数第n个节点的时候,需要修改的其实是前驱节点的next。所以在head头之前加个dummy比较方便,同时避免了需要删除的就是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

class Solution {
public:
int getLength(ListNode* head){
int length = 0;
while(head){
length++;
head = head->next;
}
return length;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
int length = getLength(head);
ListNode* dummy = new ListNode(0, head);
ListNode* cur = dummy;
for (int i = 1; i < length - n + 1; i++){
cur = cur->next;
}
cur->next = cur->next->next;
ListNode* ans = dummy->next;
delete dummy;
return ans;

}
};

方法二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(0, head)
stack = list()
cur = dummy
while cur:
stack.append(cur)
cur = cur.next

for i in range(n):
stack.pop()

prev = stack[-1]
prev.next = prev.next.next
return dummy.next

方法三:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(0, head)
second = head
first = dummy

for _ in range(n):
second = second.next
while second:
second = second.next
first = first.next

next_opt = first.next.next
first.next = next_opt
return dummy.next

双链表操作问题

不妨列举几个经典例子。

两数相加

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

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

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

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807


思路一:

在原来的l1 和 l2 上面直接修改,直接返回修改后的l1, 如果l2 的 长度大于 l1做拼接,不新建一个list。减少空间复杂度。这个思路的话,写的时候的最大问题是拼接的时候得记录尾端,使用了tail进行记录。

思路二:

直接新建一个head,记录新的和。对于两个序列长度不一,一是补0补成长度一致,二是每次进行判断,已经为空的list节点不对结果产生影响。

几个细节的地方:

1、对于操作双链表的问题,判断链表头节点是否为空:一是判断两个ListNode都为空,二是如果两个链表只有其中一个为空,直接返回另一个基本就符合答案。(当然本题题目里面已经说了两个非空)

2、由于在写的时候,思路一用的是下面这个写法,这个写法的问题是,最后一次操作会把 op1 置为 None。但是我们想要拼接操作时候,写 op1.next = op2 时候会报错。锁定一个不为空的尾端,需要我们用一个tail额外记录。

1
2
3
4
while op1:
# 对op1的一系列操作
tail = op1
op1 = op1.next

3、对于进位计算的模拟操作。善用 // 和 % 操作。

4、dummy 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

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
# if not l1 and not l2:
# return None
if not l1: return l2
if not l2: return l1

op1 = l1; op2 = l2; upgrade = 0; tail = None
while op1 and op2:
op1.val = op1.val + op2.val + upgrade
upgrade = op1.val // 10
op1.val = op1.val % 10
tail = op1
op1 = op1.next
op2 = op2.next

while op1:
op1.val = op1.val + upgrade
upgrade = False
upgrade = op1.val // 10
op1.val = op1.val % 10
tail = op1
op1 = op1.next

if op2:
tail.next = op2
while op2:
op2.val = op2.val + upgrade
upgrade = False
upgrade = op2.val // 10
op2.val = op2.val % 10
tail = op2
op2 = op2.next
if upgrade:
tail.next = ListNode(1)
return l1

思路二实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = head = ListNode(); up = 0

while l1 or l2 or up:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
temp = val1 + val2 + up
up = temp // 10
head.next = ListNode(temp % 10)
head = head.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None

return dummy.next

合并两个有序链表

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

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


我们仿照一下上面的思路,第一步是判断l1和l2是否为空,第二步是dummy 和 head的构建。第三步是 tail对于尾端的记录。第四步是公共部分大小比对完毕后的拼接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 and not l2: return None
if not l1: return l2
if not l2: return l1
dummy = head = ListNode(); tail = None
while l1 and l2:
if l1.val < l2.val:
head.next = ListNode(l1.val)
tail = head.next
l1 = l1.next
else:
head.next = ListNode(l2.val)
tail = head.next
l2 = l2.next
head = head.next
# 这边head和tail其实都在监控最后一个有效的构建节点
# 所以下面直接用head.next = l2 if l2 else l1 也行
tail.next = l2 if l2 else l1
return dummy.next