1 链表问题

必考题

1.1 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明：

给定的n保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

  • 可以考虑快慢指针来实现各种位置删除的链表

能不能用1次遍历解决这个问题呢？这里我们运用到解决这类线性列表的数据结构题目一个高频技巧，双指针。 为了方便，在原有链表前面设置一个哑结点，哑结点的好处在于，因为这里我们是要删除一个结点，所以我们可以定位到被删除结点的前置结点，然后将前置结点的后续指针指向被删除结点的后续结点，则可完成删除。

建立两个指针，l1先从第一个节点访问到第n个节点，然后l1和l2同时进行扫描，当l1扫描到链表尾时，l2恰好到倒数第n个节点。

我们设置两个指针，两个指针初始状态都指向哑结点，指针fast 先走n步，然后指针fast和指针slow同步往前继续遍历链表，直至fast的后续结点为空，此时指针slow到达被删除结点的前置结点。belinda

1.定义一个头结点，指向链表的第一个结点 2.快慢指针指向头结点 3.快指针先走n步 4.快慢指针一起走，直到快指针走到链表尾 5.慢指针后一位链接为其后一位的后一位（实现截断连接） 6.返回头结点的后一位结点。Huster2018

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        Node = ListNode(None) #哑铃节点
        Node.next = head
        first,slow = Node,Node
        for i in range(n):
            first = first.next
        while first.next != None:
            first = first.next
            slow = slow.next
        slow.next = slow.next.next #指向删除节点的后续位置
        return Node.next
  • 利用快指针fast和慢指针slow，先让快指针fast和慢指针slow都位于首节点，然后让快指针fast先走n-1步，随后慢指针slow开始走，当fast走到链表的尾节点时，slow此时正位于倒数第n个节点上。
class Solution:
    def getKthFromEnd(self,head,k):
        fast=slow=head
        if head==None or k<=0:
            return None
        while k>0 and fast !=None:
            fast=fast.next
            k-=1
        while fast!=None:
            fast=fast.next
            slow=slow.next
        return slow
  • 方法二

list法

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        res=[]
        while head:
            res.append(head)
            head=head.next
        if k>len(res) or k<1:
            return 
        return res[-k]

1.2 判断是否是环形链表

示例 3：

输入：head = [1], pos = -1 输出：false 解释：链表中没有环。

题解:也是快慢指针的问题

  • 通过使用具有不同速度的快、慢两个指针遍历链表，空间复杂度可以被降低至O(1)。慢指针每次移动一步，而快指针每次移动两步。

  • 如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 false。

  • 现在考虑一个环形链表，把慢指针和快指针想象成两个在环形赛道上跑步的运动员（分别称之为慢跑者与快跑者）。而快跑者最终一定会追上慢跑者。这是为什么呢？考虑下面这种情况（记作情况 A）- 假如快跑者只落后慢跑者一步，在下一次迭代中，它们就会分别跑了一步或两步并相遇。

  • 其他情况又会怎样呢？例如，我们没有考虑快跑者在慢跑者之后两步或三步的情况。但其实不难想到，因为在下一次或者下下次迭代后，又会变成上面提到的情况 A。

  • 方法1 快慢指针法

  • 参考阿常呓语」

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

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

        return True
  • 方法2 集合法
class Solution02:
    def hasCycle(self, head: ListNode) -> bool:
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False

1.3 链表中环的入口

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

本质上也是快慢指针的思想，但是可以有简单一点的方法

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if not pHead:
            return None
        lst = []
        while pHead:
            if pHead in lst:
                return pHead
            else:
                lst.append(pHead)
                pHead = pHead.next
        return None
  • 方法二

快慢指针的方式才是主流

第一步：如何确定一个链表中包含环。 定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个一次走两步。如果走得快的指针走上了走的慢的指针，那么链表就包含环；如果走的快的指针走到了链表的末尾都没有追上第一个指针，那么链表就不包含环。

第二步：如何找到环的入口。 慢指针回到表头，快指针留在相遇点，二者同步往前直到相遇在入口结点。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            # 如果相遇
            if slow == fast:
                p = head
                q = slow
                while p!=q:
                    p = p.next
                    q = q.next
                #你也可以return q
                return p

        return None

1.4 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 这个图解挺好的

递归法

def func3(head):
    if head.next == None:
        return head
    new_head = func3(head.next)
    head.next.next = head
    head.next = None
    return new_head

迭代法

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None or head.next==None:  # 若链表为空或者仅一个数就直接返回
          return head 
        rev,p=None,head
        while p:
          rev,rev.next,p=p,rev,p.next
        return rev

写一个过程

迭代指针：p = head、结果指针：res = none

以1->2->3->4->5为例：

过程：

res:None

第一层循环

res:1->2->3->4->5 res = p

res:1->None res.next = res

p:2->3->4->5 p = p.next

第二层循环

res:2->3->4->5 res = p

res:2->1->None res.next = res

p:3->4->5 p = p.next

第三层循环

res:3->4->5 res = p

res:3->2->1->None res.next = res

p:4->5 p = p.next

第四层循环

res:4->5 res = p

res:4->3->2->1->None res.next = res

p:5 p = p.next

第五层循环

res:5 res = p

res:5->4->3->2->1->None res.next = res

p:None p = p.next

1.5 排序链表

在O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3 输出: 1->2->3->4 示例 2:

输入: -1->5->3->4->0 输出: -1->0->3->4->5

因此这个题就是考归并排序的

递归排序三部曲：

  • 1，快慢指针找中点；
  • 2，递归调用mergeSort，
  • 3，合并两个链表

这个答案也能通过



class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not (head and head.next): return head
        pre, slow, fast = None, head, head
        while fast and fast.next: 
            pre, slow, fast = slow, slow.next, fast.next.next
        pre.next = None
        return self.mergeTwoLists(*map(self.sortList, (head, slow)))
    
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 and l2:
            if l1.val > l2.val: l1, l2 = l2, l1
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1 or l2
  • 方法2

时间复杂度是o(n)

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        t = []
        cur = head
        while cur:
            t.append(cur.val)
            cur = cur.next

        return t.sort()

至此，双指针的链表题都齐了

下面开始单指针的

1.6 回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2 输出: false 示例 2:

输入: 1->2->2->1 输出: true

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

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        t = []
        cur = head
        while cur:
            t.append(cur.val)
            cur = cur.next

        return t == t[::-1]

1.7 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例：

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

思路

  • 判断两个链表是否存在，否则返回另一个
  • 比较两个链表结点的值
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
      if not l1:
          return l2
      if not l2:
          return l1:
      while l1 and l2:
          if l1.val<=l2.val:
              l1.next=self.mergeTwoLists(l1.next,l2)
              return l1
          else: 
              l2.next=self.mergeTwoLists(l1,l2.next)
              return l2

1.8 删除链表中的结点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

示例 1:

输入: head = [4,5,1,9], node = 5 输出: [4,1,9] 解释: 给定你链表中值为5的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9. 示例 2:

输入: head = [4,5,1,9], node = 1 输出: [4,5,9] 解释: 给定你链表中值为1的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

node是待删除的结点，因此就让指向node的指针指向node的下一个结点就好了


class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val=node.next.val
        node.next=node.next.next

1.9 两两交换链表的节点

两两交换链表中的节点 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例: 给定 1->2->3->4, 你应该返回 2->1->4->3.

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

        # If the list has no node or has only one node left.
        if not head or not head.next:
            return head

        # Nodes to be swapped
        first_node = head
        second_node = head.next

        # Swapping
        first_node.next  = self.swapPairs(second_node.next)
        second_node.next = first_node

        # Now the head is the second node
        return second_node

1.10 链表相交并找出交点

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。

示例 1：

输入：listA = [4,1,8,4,5], listB = [5,0,1,8,4,5]

输出：Reference of the node with value = 8

  • 这个题的相交节点为什么不是1？

输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

这个题也是剑指offer上面的，和公共节点的题类似

解题思路： 


# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        将两个链表拼接在一起，p是headA->headB
        q是headB->headA
        这样p和q的长度一致，会在相交节点相遇
        要么就都返回None
        :param headA: ListNode
        :param headB: ListNode
        :return: ListNode
        """
        p = headA
        q = headB
        # p 4,1,8,4,5->5,0,1,8,4,5
        # q 5,0,1,8,4,5->4,1,8,4,5

        while p is not q:
            p = p.next if p else headB
            q = q.next if q else headA
        return p
  • 方法2 使用集合

集合这个更巧妙一点

class Solution():
    def getIntersectionNode(self, headA, headB):
        """

        :param headA: ListNode
        :param headB: ListNode
        :return: ListNode
        """
        s = set()
        h1 = headA
        h2 = headB
        while h1:
            s.add(h1)
            h1 = h1.next
        while h2:
            if h2 in s:
                break
            h2 = h2.next
        return h2

1.11 每k个节点反转链表

题目描述： 给出一个链表，每k个节点一组进行翻转，并返回翻转后的链表。 k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么将最后剩余节点保持原有顺序。

第一行输入是链表的值 第二行输入是K的值，K是大于或等于1的整数

输入形式为： 1 2 3 4 5 当k = 2时，应当输出: 2 1 4 3 5

当k = 3时，应当输出: 3 2 1 4 5

当k=6时，应当输出： 1 2 3 4 5

def reverseList_k(head,k):
    cur = head
    cnt = 0
    while cur and cnt != k:
        cur = cur.next
        cnt += 1
    if cnt == k:
        cur = reverseList_k(cur,k)
        while cnt:
            head.next,cur,head = cur,head,head.next
            cnt -= 1
        head = cur
    return head

1.12 两数相加

  • 题目描述

先将l1和l2头节点的值加起来赋值给新链表的头节点 遍历两个链表，只要有一个链表还没有遍历到末尾，就继续遍历 每次遍历生成一个当前节点cur的下一个节点，其值为两链表对应节点的和再加上当前节点cur产生的进位 更新进位后的当前节点cur的值 循环结束后，因为首位可能产生进位，因此如果cur.val是两位数的话，新增一个节点 返回头节点

输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807. 示例 2：

输入：l1 = [0], l2 = [0] 输出：[0] 示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]

  • 解题思路

是典型的链表指针解题，可以考虑递归

根据题意可知链表数字位数是从小到大的

因为两个数字相加会产生进位，所以使用i来保存进位。 则当前位的值为(l1.val + l2.val + i) % 10 则进位值为(l1.val + l2.val + i) / 10 建立新node，然后将进位传入下一层。

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def dfs(l, r, i):
            if not l and not r and not i: return None
            s = (l.val if l else 0) + (r.val if r else 0) + i
            node = ListNode(s % 10)
            node.next = dfs(l.next if l else None, r.next if r else None, s // 10)
            return node
        return dfs(l1, l2, 0)