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

环形链表

给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 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
}