这次题目有三题,分别是环形链表合并两个有序链表移除链表元素.
其中环形链表比较值得一看,解法有三种,感觉第一种有点骚✨

环形链表

给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos-1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回 true 。 否则,返回 false

进阶:
你能用 O(1)(即,常量)内存解决此问题吗?

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos 为 -1 或者链表中的一个 有效索引 。

解题思路&题解

这题有好几个方法解决,如下:

  1. 利用一个特殊的值覆盖已遍历的元素,当再次遇到该值时表示有回环
  2. 利用哈希表存储记录节点地址
  3. 快慢指针法(传统法)

特殊值法

这个方法感觉有点奇葩,特殊值要测试点中不存在才可以😄

1
2
3
4
5
6
7
8
9
10
11
12
13
func hasCycle(head *ListNode) bool {
for {
if head == nil {
return false
}
if head.Val == 114514{
return true
} else {
head.Val = 114514
}
head = head.Next
}
}

哈希表存储节点

这个方法只需要将链表遍历一次,但需要耗费更大的内存空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func hasCycle(head *ListNode) bool {
nodeMap := map[ListNode]int{}
node := head
for {
if node == nil {
return false
}
nodeMap[*node]++
if nodeMap[*node] > 1 {
return true
}
node = node.Next
}
}

快慢指针法

这个是传统的方法,但有可能需要遍历几次闭环,等慢指针追上快指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func hasCycle(head *ListNode) bool {
if head == nil || head.Next == nil {
return false
}
slow, fast := head, head.Next
for fast != slow {
if fast == nil || fast.Next == nil {
return false
}
slow = slow.Next
fast = fast.Next.Next
}
return true
}

合并两个有序链表

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

示例 1:

1
2
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

1
2
输入:l1 = [], l2 = []
输出:[]

示例 3:

1
2
输入:l1 = [], l2 = [0]
输出:[0]

解题思路&题解

需要注意这题有一个大前提,题目给的两个链表都是升序的,因此这题类似前面的合并两个有序数组有点类似。

  1. 通过比较头节点,小的添加到新链
  2. 遍历完其中一条链后,将另一条链直接拼接在后面
    代码如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    res := &ListNode{}
    node := res
    for {
    if l1 == nil {
    node.Next = l2
    return res.Next
    }
    if l2 == nil {
    node.Next = l1
    return res.Next
    }
    tmp := &ListNode{}
    if l1.Val <= l2.Val {
    tmp.Val = l1.Val
    l1 = l1.Next
    } else {
    tmp.Val = l2.Val
    l2 = l2.Next
    }
    node.Next = tmp
    node = node.Next
    }
    }

移除链表元素

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

示例 1:

1
2
输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]

示例 2:

1
2
输入:head = [], val = 1
输出:[]

示例 3:

1
2
输入:head = [7,7,7,7], val = 7
输出:[]

解题思路&题解

这题就是基本的删除链表元素,直接上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func removeElements(head *ListNode, val int) *ListNode {
root := &ListNode{Next: head}
node := root
for {
if node == nil {
break
}
if node.Next != nil && node.Next.Val == val {
node.Next = node.Next.Next
} else {
node = node.Next
}
}
return root.Next
}