链表算法题
#链表#LeetCode#算法 2023-12-31

链表相关算法题

题目

快慢指针

876. 链表的中间结点 - 力扣（LeetCode）

141. 环形链表 - 力扣（LeetCode）

142. 环形链表 II - 力扣（LeetCode）

143. 重排链表 - 力扣（LeetCode）

删除节点

237. 删除链表中的节点 - 力扣（LeetCode）

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

83. 删除排序链表中的重复元素 - 力扣（LeetCode）

82. 删除排序链表中的重复元素 II - 力扣（LeetCode）

LeetCode 876

思路

采用快慢指针的方法，快指针遍历链表，当快指针下标整除 2 得 0 时（也就是可以下一个中间节点了），此时慢指针向后移动。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
func middleNode(head *ListNode) *ListNode {
    var low = head
    var fast int
    for head.Next != nil{
        if fast % 2 == 0{
            low = low.Next
        }
        
        head = head.Next
        fast++
    }
    return low
}

LeetCode 141

思路

方法一

很容易想到的一个思路就是使用哈希表记录地址，当出现了重复的地址时，返回 true。

方法二

这道题被归类到快慢指针，我们也可以使用快慢指针的方法，也叫做龟兔赛跑。

初始时，慢指针位于 head，快指针位于 head.Next，每次迭代，慢指针向后移动一位，快指针向后移动两位。当快指针遍历到最后的节点（下一个节点为空时，跳出循环）。或者说，快指针与慢指针相撞时（证明这个是个环），那么返回 true。

代码实现

方法一：哈希表

1
2
3
4
5
6
7
8
9
10
11
func hasCycle(head *ListNode) bool {
    var linkMap = make(map[*ListNode]struct{})
    for head != nil && head.Next != nil{
        if _, ok := linkMap[head]; ok{
            return true
        }
        linkMap[head] = struct{}{}
        head = head.Next
    }
    return false
}

方法二：快慢指针

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

LeetCode 142

思路

这题和 141 一样也可以使用哈希表解决。

至于快慢指针，这是个数学问题，推导可见力扣官解。

那么，直接得到结论就是，链表头节点到入环点的距离，恰好等于相遇点到入环点的距离。那么，我们只需要在相遇时，初始化一个指针 ptr，然后与 low 一起向后移动，它俩相遇那么就得到了入环点。

代码实现

哈希表实现

1
2
3
4
5
6
7
8
9
10
11
func detectCycle(head *ListNode) *ListNode {
    var linkMap = make(map[*ListNode]struct{})
    for head != nil && head.Next != nil{
        if _, ok := linkMap[head]; ok{
            return head
        }
        linkMap[head] = struct{}{}
        head = head.Next
    }
    return nil
}

快慢指针实现：觉得在面试中可以不用写这个方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func detectCycle(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    var low, fast = head, head
    for fast != nil && fast.Next != nil{
        low = low.Next
        fast = fast.Next.Next
        if low == fast{
            var ptr = head
            for ptr != low{
                ptr = ptr.Next
                low = low.Next
            }
            return ptr
        }
    }
    
    return nil
}

LeetCode 143

思路

方法一

采用灵神的一句话，链表题觉着难做，转换成数组就行。

方法二

找到链表的中心节点 + 反转后半部分链表 + 合并链表

代码实现

方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func reorderList(head *ListNode)  {
    var list = make([]*ListNode, 0)
    for head != nil{
        list = append(list, head)
        head = head.Next
    }

    var i, j = 0, len(list) - 1
    for i < j{
        list[i].Next = list[j]
        i++
        if i == j{
            break
        }
        list[j].Next = list[i]
        j--
    }
    // 最后一个节点是下标为 i 的节点，它的下一个节点必须设为 nil
    // 否则会导致它的下一个是它自己
    list[i].Next = nil
}

方法二

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
43
44
45
46
47
48
49
func reorderList(head *ListNode)  {
    // 找到中心节点的开始
    low := findLinkCenterNode(head)

    // 从 low 开始到最后一个节点，反转
    pre := reverseLink(low)
    
    // 合并
    mergeLink(head, pre)
}

// findLinkCenterNode 找到链表的中心节点
func findLinkCenterNode(head *ListNode) *ListNode{
    var low, temp = head, head
    var fast int
    for temp != nil{
        if fast % 2 == 0{
            low = low.Next
        }
        fast++
        temp = temp.Next
    }
    return low
}

// reverseLink 反转链表
func reverseLink(head *ListNode) *ListNode{
    var pre *ListNode
    var cur = head
    for cur != nil{
        temp := cur.Next
        cur.Next = pre
        pre = cur
        cur = temp
    }
    return pre
}

// mergeLink 合并链表
func mergeLink(left, right *ListNode){
    for left != nil && right != nil{
        var ln, rn = left.Next, right.Next
        left.Next = right
        right.Next = ln
        left = ln
        right = rn
    }
    left.Next = nil
}

LeetCode 237

思路

因为不是在内存中删除，我们只需要：

  1. 从当前需要删除的节点开始，将当前节点的值赋值为下一个节点的值。
  2. 然后当当前节点的后第二个节点为空时，证明下一个节点为最后一个节点，将最后一个节点舍去，也就是此时当前节点设为空。

代码实现

1
2
3
4
5
6
7
8
9
10
func deleteNode(node *ListNode) {
    for node.Next != nil{
        node.Val = node.Next.Val
        if node.Next.Next == nil{
            node.Next = nil
            break
        }
        node = node.Next
    }
}

LeetCode 19

思路

自己的想法

首要想法是遍历两遍链表。

我采用遍历一遍链表，就是将链表转为数组，然后计算出要删除的节点，但是会占用额外的空间。

看了题解后的改进

双指针法，我觉得这个解法真的很巧妙。

定义一个快慢指针，快指针比慢指针先多走 n 个，也就是两个指针的距离为 n + 1，当快指针到链表尾部的时候（也就是此时 fast 为空指针），慢指针就到了链表倒数第 n + 1 个。

代码实现

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 removeNthFromEnd(head *ListNode, n int) *ListNode {
    var list = make([]*ListNode, 0)
    var res = head
    for head != nil{
        list = append(list, head)
        head = head.Next
    }

    deleteNode := len(list) - n
    if deleteNode > 0 {
        pre := deleteNode - 1
        if pre + 2 > len(list) - 1{
            list[pre].Next = nil
        }else{
            list[pre].Next = list[pre + 2]
        }
        return res
    }
    if deleteNode == 0 && len(list) > 1{
        return list[1]
    }

    return nil
}

改进算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    var dummy = &ListNode{0, head}
    var low, fast = dummy, head
    for i := 0; i < n; i++{
        fast = fast.Next
    }

    for ; fast != nil; fast = fast.Next{
        low = low.Next
    }

    // 此时 low.Next 就是要删除节点
    low.Next = low.Next.Next
    return dummy.Next
}

LeetCode 83

思路

有一个一下子想到的思路是使用哈希表记录，然后有相同的就删除。

我的思路就是，在遍历的时候记录下上一个节点，如果和上一个节点的值一样，将上一个节点的值设置为本节点的下一个节点，然后不更新 pre。不一样则更新 pre。

简单题重拳出击。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
func deleteDuplicates(head *ListNode) *ListNode {
    var res = head
    var pre = &ListNode{101, head}
    for ; head != nil; head = head.Next{
        if head.Val == pre.Val{
            pre.Next = head.Next
            continue
        }
        pre = head
    }
    return res
}

LeetCode 82

思路

本题其实和上题差不多，这题在于多了个哨兵节点。

当我们在遍历时，先判断是否有下两个节点。

  1. 如果有，获取下两个节点的值。当下两个节点的值相等时，我们遍历下一个节点，使当前节点的下一个节点指向下一个不相等的节点。
  2. 无，直接退出即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil{
        return head
    }

    dummy := &ListNode{0, head}
    cur := dummy

    for cur.Next != nil && cur.Next.Next != nil{
        if cur.Next.Val == cur.Next.Next.Val{
            var x = cur.Next.Val
            // 当遍历到不是相同元素的时候，就退出循环
            for cur.Next != nil && cur.Next.Val == x{
                cur.Next = cur.Next.Next
            }
        }else{
            cur = cur.Next
        }
    }
    return dummy.Next
}