[leetcode刷题笔记]链表的递归、双指针解法

链表是基础的数据结构，在作链表算法时，除了使用暴力循环的方法外（很多时候暴力方法会造成超时不可取），还有一些其他方法，如递归，双指针法，哈希表法等。本文记录LeetCode刷题一些知识点，水平有限还望多多指正

1.删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

使用递归可以使代码简化很多。

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if head == None:
            return None
        if head.val == val:
            return head.next
        head.next = self.deleteNode(head.next,val)
        return head

2.合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2
        if not l2:
            return l1
    
        if l1.val <= l2.val:
            l1.next = self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1,l2.next)
            return l2

3.环形链表

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

快慢指针法，这是通过这道题新学到的方法，就像两个环形跑道上跑步快慢的运动员，若存在环，则快指针能够追上慢指针，这在检测是否有环很实用。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False
    
        slow = head
        fast = head

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

            if slow == fast:
                return True
            if not fast:
                return False

        return False

4.相交链表

编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：

在节点 c1 开始相交。

双指针法 两个指针分别指向headA与headB，以此向后比较，当 p 到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B); 类似的，当 q 到达链表的尾部时，将它重定位到链表 A 的头结点。若某一时刻p=q，则为交点。

若存在交点经过O(m+n)时间一定能找到交点。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        p,q = headA,headB
        while p!=q:
            p = p.next if p else headB
            q = q.next if q else headA
        return p 

题目和部分解析来源力扣（LeetCode）,更多内容后续补充，欢迎指正。