Leetcode常见链表问题及代码示例

链表是面试中出现频率很高的数据结构，掌握链表相关问题对于应聘者来说非常重要。

本篇攻略将介绍Leetcode中常见的链表问题并提供对应的代码示例，方便读者理解和练习。

1. 链表反转

题目描述：反转一个单链表。

主要思路：从前往后遍历原链表，每次将遍历到的节点移动到反转链表的头部。

实现代码：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur = head
        pre = None

        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp

        return pre

2. 链表的中间节点

题目描述：给定一个带有头结点 head 的非空单链表，返回链表的中间节点。

主要思路：使用快慢指针，快指针走两步，慢指针走一步，当快指针到达末尾时，慢指针正好在中间节点。

实现代码：

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow, fast = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        return slow

3. 链表中倒数第 k 个节点

题目描述：找到单链表中倒数第 k 个节点。

主要思路：使用双指针，先让快指针先走k步，然后再让慢指针和快指针同时往前走，直到快指针到达末尾时，慢指针正好到达倒数第k个节点。

实现代码：

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        slow, fast = head, head

        for i in range(k):
            fast = fast.next

        while fast:
            slow = slow.next
            fast = fast.next

        return slow

4. 合并两个有序链表

题目描述：将两个升序链表合并为一个新的升序链表。

主要思路：定义一个新链表，然后依次比较两个原链表当前节点的大小，将较小的节点“接”在新链表的最后面。

实现代码：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        cur = dummy

        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next

            cur = cur.next

        if l1:
            cur.next = l1
        if l2:
            cur.next = l2

        return dummy.next

5. 链表中的环

题目描述：给定一个链表，判断链表中是否有环。

主要思路：使用快慢指针，快指针每次走两步，慢指针每次走一步，如果快慢指针在某个时刻相遇了，那么说明链表中有环。

实现代码：

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow, fast = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True

        return False

以上是本攻略总结的5道常见的链表问题的解题思路和代码实现示例，读者可以根据需要进行练习和拓展。