[数据结构与算法]leetcode2021年度刷题分类型总结（六）链表 （python）

参考：代码随想录
首先总结一下自己对链表的概念容易混淆的地方：
单向链表的定义：链表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向NULL的指针。
1.头指针head
头指针head，指向头节点。当链表不为空时，head.val即为头节点的值；而当链表为空时，head.val会报错，因为head此时指向null，没有.val属性。
无论链表是否为空，头指针均不为空。具体来说，即头指针本身不能为空，它一定存在，不论指向的是空，还是指向的是头结点。如果头指针为空，那么它无法指向任何地方。
2.结尾处的None
此处需要注意，结尾处的None不是一个节点，也即不是ListNode(None),而是None。在做比如翻转链表类题的时候容易混淆。
3.链表题常见的错误：
1）超出时间限制。说明链表大概率哪里连接错误了，有可能连成了圈
2）Nonetype没有val和next属性，极有可能是循环或者递归的时候对于链表的边界没有处理好，对最后的None也用了val和next属性

例一：203. 移除链表元素

203. 移除链表元素
要注意头节点的移除和其他节点的移除不一样，头节点移除：head=head.next
其他节点移除：head.next=head.next.next

思路一：写一段代码来单独移除头节点

分成两种情况考虑。第一种情况是头节点非空，且头节点的值就是val。假设后续返回head，此时需要直接对后续返回的head进行处理，把head=head.next，即删除头节点
如果不是第一种情况，对head赋值给head_copy，若head_copy指向的下一节点值为val，
通过head_copy.next=head_copy.next.next删除下一节点，否则head_copy=head_copy.next，head_copy指针移到下一位置。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        head_copy=head
        if not head:
            return None

        while head!=None and head.val==val:
            head=head.next

        while head_copy.next:
            if head_copy.next.val==val:
                head_copy.next=head_copy.next.next
            else:
                head_copy=head_copy.next

        return head

存在重复处理的缺点，时间复杂度高。
比如处理链表[7,7,7,7]，
经过

        while head!=None and head.val==val:
            head=head.next

head链表已经为空了，但是head_copy依旧是[7,7,7,7]，所以还要经过以下代码

        while head_copy.next:
            if head_copy.next.val==val:
                head_copy.next=head_copy.next.next
            else:
                head_copy=head_copy.next

得到head_copy为[7]，然后最后返回head为空，可以优化：处理完头节点值等于val后再赋给head_copy，快个几毫秒，代码如下：

class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
       
        if not head:
            return None

        while head!=None and head.val==val:
            head=head.next

        if not head:
            return None
        else: 
            head_copy=head


        while head_copy.next:
            if head_copy.next.val==val:
                head_copy.next=head_copy.next.next
            else:
                head_copy=head_copy.next

        return head

思路二：添加一个虚拟头结点为新的头结点

为了保持格式一致，即对头结点也使用head.next=head.next.next格式的删除方法，可以添加一个虚拟的头结点作为新的头结点。但是要注意返回的时候return dummy_head.next

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """

        dummy_head=ListNode(next=head)
        cur=dummy_head
        while cur.next:
            if cur.next.val==val:
                cur.next=cur.next.next
            else:
                cur=cur.next
        return dummy_head.next

例二：翻转链表

翻转链表

方法一：双指针法

其实这里可以理解为需要三个指针，一个初始化为None的pre作为新链表的尾部，一个head作为目前所在节点，一个nextnode记录下一个节点的位置。
1）当head不为None时，head.next一定存在，把head.next用nextnode指针记录。
2）head.next指针指向pre
3) pre=head,head=nextnode(也即pre和head指针都往下走一步)
这里一定要注意的是nextnode记录下一个节点的位置的步骤必不可少，因为一旦head.next=pre，如果没有nextnode记录下head要去的下一个位置，那链表的head指针没法继续往下走

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        prev=None
        
        
        while head:
            nextnode=head.next
            head.next=prev
            prev=head #prev记载head呆过的地方
            head=nextnode



        return prev

方法二：递归法

思路跟双指针法一样，就是while循环的终止条件设置成递归结束的条件，然后每次while循环的执行都用递归循环来代替。
可以对比学习一下自己写的递归和别人写的递归，很明显自己的代码可以写的更简洁一点。直接return nextstep(cur,nextnode)，而不用res=nextstep(cur,nextnode) 再return res

自己的版本：

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        def nextstep(pre,cur):
            if not cur:
                return pre
            nextnode=cur.next
            cur.next=pre
            res=nextstep(cur,nextnode)
            return res

        pre=None
        cur=head
        result=nextstep(pre,cur)
        return result

别人的版本：

class Solution:
    def reverseList(self, head):
        
        def reverse(pre,cur):
            if not cur:
                return pre
                
            tmp = cur.next
            cur.next = pre

            return reverse(cur,tmp)
        
        return reverse(None,head)

例三：24. 两两交换链表中的节点

24. 两两交换链表中的节点
这里最好要加一个虚拟头节点dummyHead来简化代码。有两点方便
第一是可以把交换节点的过程统一化，如下图（图源：代码随想录）

(写代码时，上图中的步骤二和步骤三应该对调，不然经过步骤二，值为2的节点的下一节点已经是值为1的节点，这样无法到达值为3的节点)

然后步骤一1–>4；步骤二： 4–>3 步骤三：3–>4，过程更规范化。
第二点是返回链表头部的方便，可以直接return dummyHead.next。如果不用虚拟头节点，由于此时head不再是初始节点，整个链表怎么返回也是个问题。

具体思路：如上图所示，先设置一个虚拟头节点，之后可以分别通过上图中的步骤一、步骤三、步骤二来达到交换节点的目的。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummyHead = ListNode(0)
        dummyHead.next = head
        temp = dummyHead
        while temp.next and temp.next.next:
            node1 = temp.next
            node2 = temp.next.next
            temp.next = node2 #步骤一
            node1.next = node2.next #步骤三
            node2.next = node1 #步骤二
            temp = node1 #到下一位置
        return dummyHead.next

例四：19. 删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点

方法一：两次遍历

第一遍遍历数链表中节点个数，第二遍数目前所在节点数，如果到了倒数第n个节点，删除它

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        #方法一：两趟扫描，第一趟数链表数，确定需要删除的结点，第二趟删除结点
        #两种特殊情况：链表只有一个结点；链表结点数==n
        



        cur_node=head
        cnt=0

        while cur_node:
            cnt+=1
            cur_node=cur_node.next
        
        if cnt==1:
            return None  #链表只有一个结点

        #链表结点数==n，删除首结点
        if cnt==n:
            head=head.next
            return head 

        #要删除的结点序号 cnt-n
        opr_node=head
        temp=0
        while opr_node:
            if temp==cnt-n-1:
                opr_node.next=opr_node.next.next
                opr_node=opr_node.next
                temp+=1
            else:
                temp+=1
                opr_node=opr_node.next    
        
        return head

方法二：双指针一次遍历

只允许一次遍历。用两个指针，指针间距离设置成n,第一个指针初始化为头节点。两个指针同时运动，这样第二个指针到链表尾部时，第一个指针指向的就是要删除的节点

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        #方法一：第一遍遍历数链表中节点个数，第二遍数目前所在节点数，如果到了倒数第n个节点，删除它
        #方法二：只允许一次遍历。用两个指针，指针间距离设置成n,第一个指针初始化为头节点。两个指针同时运动，这样第二个指针到链表尾部时，第一个指针指向的就是要删除的节点
        dummyhead=ListNode(0)
        dummyhead.next=head
        prevfirstnode=dummyhead
        firstnode=head
        secondnode=firstnode
        while n:
            n-=1
            secondnode=secondnode.next
        # print("step1 yes")

        while secondnode:
            prevfirstnode=prevfirstnode.next
            firstnode=firstnode.next
            secondnode=secondnode.next
        # print("step2 yes")

        prevfirstnode.next=firstnode.next
        return dummyhead.next

例五：面试题 02.07. 链表相交

面试题 02.07. 链表相交
链表的相交用比较经典的双指针，“走你走过的路”。但是有一个自己容易出错的地方在于：
当headA或者headB走到下一节点为None的时候，就把它调回另外一链表的头部，这样可以通过大部分的测试用例，但是不能通过当其中一个链表只有一个节点，但是和另一链表相交的情况。
正确的用法应该是：当headA或者headB走到尾部None的时候，再把它调回另外一链表的头部

错误版代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        #双指针，“走你走过的路”
        if not headA or not headB:
            return None
        #当其中一个链表只有一个节点，但是和另一链表相交的情况
        headAcopy=headA
        headBcopy=headB
        # if headA==headB:
        #     return headA

        while headA.next or headB.next:
            if headA==headB:
                return headA
            if not headA.next:
                headA=headBcopy
                headB=headB.next
                continue
            if not headB.next:
                headB=headAcopy
                headA=headA.next
                continue
            headA=headA.next
            headB=headB.next
        return None #都为空

正确版代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        #双指针，“走你走过的路”
        if not headA or not headB:
            return None
        #当其中一个链表只有一个节点，但是和另一链表相交的情况
        headAcopy=headA
        headBcopy=headB
        # if headA==headB:
        #     return headA

        while headA or headB:
            if headA==headB:
                return headA
            if not headA:
                headA=headBcopy
                headB=headB.next
                continue
            if not headB:
                headB=headAcopy
                headA=headA.next
                continue
            headA=headA.next
            headB=headB.next
        return None #都为空

例六：141. 环形链表\142. 环形链表 II

141. 环形链表
142. 环形链表 II
判断环形链表类的题目一般都是用快慢指针算法，即fast指针和slow指针都从头节点出发，fast指针一下迈两步，slow指针一下迈一步，如果链表中存在环，那么fast和slow节点一定会相遇。
141. 环形链表只要求返回是否存在环，但是142. 环形链表 II还要求返回环的入口索引。容易产生的问题如下：
1.为什么有环的链表中，快慢指针一定会相遇？
首先，不管是怎样的链表（除了单个节点自动成环的情况），快指针一定比慢指针先入环。而入环后，假设快慢指针不相遇，那么快慢指针都可以看成在无限长圆环状的链表上一直走，而这个走的过程，由于快指针迈两步，慢指针迈一步，快指针每次迈步都在向慢指针逼近一步，快指针早晚会追上慢指针，最终相遇，且一定是在慢指针在环内的第一圈相遇（为什么？）。

2.怎么确定环的入点索引？
需要推导过程，这里讲的很清楚。过程简单点总结就是从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

141. 环形链表

不够优雅版代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        #单节点自动成环
        #只有两个节点，成或不成环
        if not head:
            return False
        fast=head
        slow=head
        #单节点无环
        if not fast.next:
            return False
        #单节点有环
        if slow.next==fast.next.next:
            return True
        #两节点无环：
        if not fast.next.next:
            return False
        #两节点有环,及其他
        while fast.next.next:
            fast=fast.next.next
            slow=slow.next
            if slow==fast:
                return True
            if not fast.next:
                return False

        return False

更优雅点的代码

跟上面代码逻辑一样，就是简化了一下，上面提到的情况也都包括了

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """

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

        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next
            if slow==fast:
                return True

        return False

142. 环形链表 II