Leetcode GO

Leetcode.剑指offer22

Posted by 凌非晨 on 2021-09-02
Estimated Reading Time 1 Minutes
Words 289 In Total
Viewed Times

题目标签

双指针、链表

解题思路一

第一次遍历计算出链表长度n，第二次遍历至n - k处即为答案

AC代码一

1
2
3
4
5
6
7
8
9
10
11
func getKthFromEnd(head *ListNode, k int) (kth *ListNode) {
    n := 0
    for node := head; node != nil; node = node.Next {
        n++
    }
    for kth = head; n > k; n-- {
        kth = kth.Next
    }
    return
}

解题思路二

使用快慢指针fast、slow进行遍历，快指针fast先遍历至第k + 1个节点,此时两个指针间相差k个节点，然后fast和slow同时向后遍历，当fast指向链表尾部后,slow指针指向倒数第k节点

AC代码二

1
2
3
4
5
6
7
8
9
10
11
12
func getKthFromEnd(head *ListNode, k int) *ListNode {
    fast, slow := head, head
    for fast != nil && k > 0 {
        fast = fast.Next
        k--
    }
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    return slow
}

解题思路三

通过for循环遍历链表记录该链表长度，同时将遍历时的首节点start保存至数组ans中，最后返回ans[len(ans) - k]

AC代码三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func getKthFromEnd(head *ListNode, k int) *ListNode {
	start := head
	ans := make([]*ListNode, 0)
	ans = append(ans, start)
	count := 1
	for start != nil {
		start = start.Next
		if start != nil {
			ans = append(ans, start)
			count++
		}
	}
	return ans[count-k]
}

如果您喜欢此博客或发现它对您有用，则欢迎对此发表评论。 也欢迎您共享此博客，以便更多人可以参与。 如果博客中使用的图像侵犯了您的版权，请与作者联系以将其删除。 谢谢 ！

特色标签
Leetcode GO
ESC