链表
# 链表的基本操作
# 翻转链表
206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
有递归法和非递归法这两种，先说一下递归法
type ListNode struct {
Val int
Next *ListNode
}
func reverseList(head *ListNode) *ListNode {
return reverse(head,nil)
}
// 递归法翻转链表，这里我们需要传入头节点和前一个节点
func reverse(head *ListNode,pre *ListNode) *ListNode {
// 当头节点为空时，我们返回前一个节点
if head==nil {
return pre
}
// 先记录下一个节点
next:=head.Next
// 这里我们知道前一个节点了，下面我们就翻转一下
head.Next = pre
// 最后我们返回的节点
return reverse(next,head)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
非递归写法如下
func reverseList(head *ListNode) *ListNode {
// 下面这个是递归写法
// return reverse(head,nil)
// 我们使用非递归写法来实现
var pre *ListNode
var next *ListNode
// 当head为空时我们结束循环
for head != nil {
// 先记录下一个节点
next = head.Next
// 下一个节点指向前一个节点
head.Next = pre
// 前一个节点head
pre = head
// 然后我们head往后移
head = next
}
return pre
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 合并有序链表
21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
这里同样分为递归的方法和非递归的方法，非递归的方法如下
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy:=&ListNode{Val:0}
node:=dummy
// 不断进行遍历,有一个为空，我们就退出循环
for l1 != nil && l2!=nil {
// 找到一个大的值进行拼接
if l1.Val >= l2.Val {
node.Next = l2
l2=l2.Next
} else {
node.Next = l1
l1=l1.Next
}
node=node.Next
}
// 把未接上的节点接到当前节点的后面去
if l1 != nil {
node.Next = l1
}else if l2 != nil{
node.Next = l2
}
return dummy.Next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
递归的方法如下，这个多理解吧，我也不好解释
// 递归解法
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
// 有一个为空时，我们直接返回另一个就行了
if l2==nil{
return l1
}else if l1==nil {
return l2
}
// 当l1当前的值大于l2时，我们接上l2的剩余部分
if l1.Val > l2.Val {
l2.Next = mergeTwoLists(l1,l2.Next)
return l2
}
// 把l1的剩余部分合并一下
l1.Next = mergeTwoLists(l1.Next,l2)
return l1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 两两交换链表中的节点
24. 两两交换链表中的节点 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
# 其他连表技巧
# 相交链表
160. 相交链表 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
# 回文链表
234. 回文链表 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
编辑 (opens new window)
上次更新: 2021/03/27, 21:55:03