环形链表

给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

  1. class Solution(object):
  2.     def hasCycle(self, head):
  3.         # 快慢指针，一个走一步，一个走两步
  4.         cur = head
  5.         pre = head
  7.         while cur and cur.next:
  8.             pre = pre.next
  9.             cur = cur.next.next
  10.             if cur is pre:
  11.                 return True
  12.         return False

环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
链表 - 图1
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

  1. class Solution(object):
  2.     def detectCycle(self, head):
  3.         cur = head
  4.         pre = head
  6.         while cur and cur.next:
  7.             pre = pre.next
  8.             cur = cur.next.next
  9.             if cur == pre: 
  10.                 res = head  # 此时res与pre距离环入口相等
  11.                 while pre != res:
  12.                     res = res.next
  13.                     pre = pre.next
  14.                 return res
  15.         return None

相交链表

编写一个程序，找到两个单链表相交的起始节点。
链表 - 图2
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

  1. class Solution(object):
  2.     def getIntersectionNode(self, headA, headB):
  3.         cur = headA
  4.         pre = headB
  6.         while cur != pre:
  7.             if cur:
  8.                 cur = cur.next
  9.             else:
  10.                 cur = headB
  11.             if pre:
  12.                 pre = pre.next
  13.             else:
  14.                 pre = headA
  15.         return cur

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
输入：head = [1], n = 1
输出：[]
输入：head = [1,2], n = 1
输出：[1]

  1. class Solution(object):
  2.     def removeNthFromEnd(self, head, n):
  4.         # 创建一个头，然后cur先跑n步，然后再一起跑
  5.         node = ListNode(0, head)
  6.         cur = node
  7.         pre = node
  9.         for _ in range(n):
  10.             if cur == None:
  11.                 return []
  12.             cur = cur.next
  14.         while cur.next is not None:
  15.             cur = cur.next
  16.             pre = pre.next
  18.         pre.next = pre.next.next
  19.         return node.next

链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

  1. class Solution:
  2.     def getKthFromEnd(self, head):
  3.         # cur先跑n步，然后再一起跑
  4.         cur = head
  5.         pre = head
  7.         for _ in range(k):
  8.             if cur == None:
  9.                 return cur
  10.             cur = cur.next
  12.         while cur != None:
  13.             cur = cur.next
  14.             pre = pre.next
  16.         return pre

移除链表元素

给你一个链表的头节点head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回新的头节点。
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
输入：head = [], val = 1
输出：[]

  1. class Solution(object):
  2.     def removeElements(self, head, val):
  3.         node = ListNode(0, head)
  4.         cur = head
  5.         pre = node
  7.         while cur:
  8.             if cur.val == val:
  9.                 pre.next = cur.next
  10.             else:
  11.                 pre = pre.next
  12.             cur = cur.next
  13.         return node.next

删除排序链表中的重复元素

存在一个按升序排列的链表，给你这个链表的头节点head，请你删除所有重复的元素，使每个元素只出现一次。
返回同样按升序排列的结果链表。
输入：head = [1,1,2]
输出：[1,2]
输入：head = [1,1,2,3,3]
输出：[1,2,3]

  1. class Solution(object):
  2.     def deleteDuplicates(self, head):
  3.         # 方法一：用假头，II题是这种思路
  4.         if not head:
  5.             return head
  7.         node = ListNode(0)
  8.         node.next = head
  9.         cur = node
  10.         while cur.next and cur.next.next:
  11.             if cur.next.val == cur.next.next.val:
  12.                 cur.next = cur.next.next
  13.             else:
  14.                 cur = cur.next
  15.         return node.next
  17.         # 方法二：不用假头
  18.         if not head:
  19.             return head
  21.         cur = head
  22.         while cur.next:
  23.             if cur.val == cur.next.val:
  24.                 cur.next = cur.next.next
  25.             else:
  26.                 cur = cur.next
  27.         return head

删除排序链表中的重复元素 II

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
输入：head = [1,1,1,2,3]
输出：[2,3]

  1. class Solution(object):
  2.     def deleteDuplicates(self, head):
  3.         # 方法一：和I类似，就多了两行代码，需要多次去判断是否相等
  4.         if not head:
  5.             return head
  7.         node = ListNode(0)
  8.         node.next = head
  9.         cur = node
  11.         while cur.next and cur.next.next:
  12.             if cur.next.val == cur.next.next.val:
  13.                 tmp = cur.next.val
  14.                 while cur.next and cur.next.val == tmp:
  15.                     cur.next = cur.next.next
  16.             else:
  17.                 cur = cur.next
  19.         return node.next

奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL

  1. class Solution(object):
  2.     def oddEvenList(self, head):
  3.         if not head:
  4.             return head
  5.         # 奇数链
  6.         cur = head
  7.         # 偶数链
  8.         pre = cur.next
  9.         # 保存偶数链头
  10.         tmp = pre
  12.         while cur.next and cur.next.next:
  13.             # 分家，拆成奇数链和偶数链
  14.             cur.next = cur.next.next
  15.             pre.next = pre.next.next
  16.             cur = cur.next
  17.             pre = pre.next
  19.         # 合并，奇数链指向偶数链
  20.         cur.next = tmp
  21.         return head

回文链表

请判断一个链表是否为回文链表。
输入: 1->2
输出: false
输入: 1->2->2->1
输出: true

  1. class Solution(object):
  2.     def isPalindrome(self, head):
  3.         # 这个方法性能太差了
  4.         lists = []
  5.         cur = head
  6.         while cur:
  7.             lists.append(cur.val)
  8.             cur = cur.next
  9.         if lists == lists[::-1]:
  10.             return True
  11.         else:
  12.             return False

合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
输入：l1 = [], l2 = []
输出：[]

  1. class Solution(object):
  2.     def mergeTwoLists(self, l1, l2):
  3.         # 方法一：递归，下面那个合并k个借鉴这个
  4.         if l1 is None:
  5.             return l2
  6.         if l2 is None:
  7.             return l1
  9.         node1 = l1
  10.         node2 = l2
  11.         if node1.val < node2.val:
  12.             node1.next = self.mergeTwoLists(node1.next, node2)
  13.             return node1
  14.         else:
  15.             node2.next = self.mergeTwoLists(node1, node2.next)
  16.             return node2
  18.         # 方法二：双指针
  19.         cur = l1
  20.         pre = l2
  21.         node = ListNode(0)
  22.         mid = node
  23.         while cur and pre:
  24.             if cur.val <= pre.val:
  25.                 mid.next = cur
  26.                 cur = cur.next
  27.             else:
  28.                 mid.next = pre
  29.                 pre = pre.next
  30.             mid = mid.next
  31.         if pre == None:
  32.             mid.next = cur
  33.         else:
  34.             mid.next = pre
  35.         return node.next

合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

  1. class Solution(object):
  2.     def mergeKLists(self, lists):
  3.         # 方法一：sort排序，暴力法
  4.         nodes = []
  5.         head = point = ListNode(0)
  7.         # 把所有元素都遍历出来放到列表中排序
  8.         for cur in lists:
  9.             while cur:
  10.                 nodes.append(cur.val)
  11.                 cur = cur.next
  13.         nodes.sort()        
  14.         for x in nodes:
  15.             point.next = ListNode(x)
  16.             point = point.next
  17.         return head.next
  19.         # 方法一：不用sort，用堆排序
  20.         nodes = []
  21.         head = point = ListNode(0)
  23.         for cur in lists:
  24.             while cur:
  25.                 heapq.heappush(nodes, cur.val)
  26.                 cur = cur.next
  28.         while nodes:
  29.             point.next = ListNode(heappop(nodes))
  30.             point = point.next
  31.         return head.next
  34.         # 方法二：优先队列堆排序，每次只移动弹出元素所在列表，所以优先队列中不仅储存链表的元素，还要存储链表所在位置，以便弹出时知道该元素属于是哪一个链表。
  35.         head = ListNode(0)
  36.         pre = head
  37.         nodes = []
  38.         for key in range(len(lists)):
  39.             if lists[key]:
  40.                 heapq.heappush(nodes, (lists[key].val, key))
  41.                 lists[key] = lists[key].next
  43.         while nodes:
  44.             value, key = heapq.heappop(nodes)
  45.             pre.next = ListNode(value)
  46.             pre = pre.next
  47.             if lists[key]:
  48.                 heapq.heappush(nodes, (lists[key].val, key))
  49.                 lists[key] = lists[key].next
  50.         return head.next
  53.         # 方法三：分治法，最优解，每次将链表列表分为两个部分，并分别自底向上合并两部分的链表
  55.         if len(lists) == 0: 
  56.             return None
  57.         if len(lists) == 1: 
  58.             return lists[0]
  59.         mid = len(lists) // 2
  61.         # 递归
  62.         def mergeTwoLists(node1, node2):
  63.             if not node1:
  64.                 return node2
  65.             if not node2:
  66.                 return node1
  67.             if node1.val < node2.val:
  68.                 node1.next = mergeTwoLists(node1.next, node2)
  69.                 return node1
  70.             else:
  71.                 node2.next = mergeTwoLists(node1, node2.next)
  72.                 return node2  
  73.         return mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:]))

两数相加*

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入：l1 = [2,4,3], l2 = [5,6,4]输出：[7,0,8]
解释：342 + 465 = 807
输入：l1 = [0], l2 = [0]
输出：[0]

  1. class Solution(object):
  2.     def addTwoNumbers(self, l1, l2):
  3.         count = 0
  4.         node = ListNode()
  5.         cur = node
  7.         while l1 or l2 or count:
  8.             num = 0
  9.             if l1:
  10.                 num += l1.val
  11.                 l1 = l1.next
  12.             if l2:
  13.                 num += l2.val
  14.                 l2 = l2.next
  15.             if count:
  16.                 num += count
  17.                 count -= 1
  18.             count, num = divmod(num, 10)
  19.             cur.next = ListNode(num)
  20.             cur = cur.next
  21.         return node.next

反转链表

反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL

  1. class Solution(object):
  2.     def reverseList(self, head):
  3.         cur = head
  4.         pre = None
  5.         while cur:
  6.             # 记录当前节点的下一个节点
  7.             tmp = cur.next
  8.             # 然后将当前节点指向pre
  9.             cur.next = pre
  10.             # pre和cur节点都前进一位
  11.             pre = cur
  12.             cur = tmp
  13.         return pre
  15. # Go语言版    
  16. func reverseList(head *ListNode) *ListNode {
  17.     var pre *ListNode
  18.     cur := head
  19.     for cur != nil {
  20.         tmp := cur.Next
  21.         cur.Next = pre
  22.         pre = cur
  23.         cur = tmp
  24.     }
  25.     return pre
  26. }

反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
输入：head = [5], left = 1, right = 1
输出：[5]

  1. class Solution(object):
  2.     def reverseBetween(self, head, left, right):
  3.         # 方法一：比较好理解
  4.         dummy = ListNode()
  5.         dummy.next = head
  6.         pre = dummy
  7.         # 找到翻转链表部分的前一个节点, 1->2->3->4->5->NULL, m = 2, n = 4 指的是 节点值为1
  8.         for _ in range(left-1):
  9.             pre = pre.next
  11.         # 用双指针,进行链表翻转
  12.         node = None
  13.         cur = pre.next
  14.         # cur多走一步到5
  15.         for _ in range(right-left+1):
  16.             tmp = cur.next
  17.             cur.next = node
  18.             node = cur
  19.             cur = tmp
  20.         # 将翻转部分 和 原链表拼接
  21.         pre.next.next = cur # 也就是1.next.next = 5
  22.         pre.next = node # 1.next = 新反转的链表
  23.         return dummy.next
  26.         # 方法二：将节点3插入节点1和节点2之间，变成: 1->3->2->4->5->NULL，再将节点4插入节点1和节点3之间，变成:1->4->3->2->5->NULL
  27.         node = ListNode()
  28.         node.next = head
  29.         pre = node
  30.         for _ in range(left - 1):
  31.             pre = pre.next
  33.         # 用 pre, cur, tmp三指针实现插入操作
  34.         # tail 是插入pre,与pre.next的节点
  35.         cur = pre.next
  36.         tmp = cur.next
  37.         for _ in range(right - left):
  38.             cur.next = tmp.next
  39.             tmp.next = pre.next
  40.             pre.next = tmp
  41.             tmp = cur.next
  42.         return node.next

链表向右移动K个位置*

给你一个链表的头节点head，旋转链表，将链表每个节点向右移动 k个位置。
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
输入：head = [0,1,2], k = 4
输出：[2,0,1]

  1. class Solution(object):
  2.     def rotateRight(self, head, k):
  3.         # 找到原链表的最后一个节点，将其与原链表的头结点相连（成环），并统计链表长度，更新有效 k 值
  4.         # 从原链表的头节点出发，找到需要断开的点，进行断开
  5.         if not head or k == 0:
  6.             return head
  8.         tmp = 0
  9.         cur = head
  10.         while cur.next:
  11.             cur = cur.next
  12.             tmp += 1
  14.         tmp += 1
  15.         k %= tmp
  16.         cur.next = head
  17.         k = tmp - k - 1
  18.         while k > 0:
  19.             head = head.next
  20.             k -= 1
  21.         ans = head.next
  22.         head.next = None
  23.         return ans

重排链表*

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

  1. class Solution(object):
  2.     def reorderList(self, head):
  3.         if not head: 
  4.             return head
  5.         # 1 2 3 4 5
  6.         fast = head
  7.         pre_mid = head
  8.         # 找到中点, 偶数个找到时上界那个
  9.         while fast.next and fast.next.next:
  10.             pre_mid = pre_mid.next
  11.             fast = fast.next.next
  13.         # 翻转中点之后的链表,采用是pre, cur双指针方法
  14.         pre = None
  15.         cur = pre_mid.next
  16.         # 1 2 3 5 4 
  17.         while cur:
  18.             tmp = cur.next
  19.             cur.next = pre
  20.             pre = cur
  21.             cur = tmp
  22.         # 翻转链表和前面链表拼接
  23.         pre_mid.next = pre
  25.         # 1 5 2 4 3
  26.         # 链表头
  27.         p1 = head
  28.         # 翻转头
  29.         p2 = pre_mid.next
  30.         while p1 != pre_mid:
  31.             # 建议这部分画图, 很容易理解
  32.             pre_mid.next = p2.next
  33.             p2.next = p1.next
  34.             p1.next = p2
  35.             p1 = p2.next
  36.             p2 = pre_mid.next
  37.         return head

两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
输入：head = [1,2,3,4]
输出：[2,1,4,3]
输入：head = []
输出：[]

  1. class Solution(object):
  2.     def swapPairs(self, head):
  3.         # 方法一：双指针
  4.         node = ListNode(0)
  5.         node.next = head
  6.         tmp = node
  7.         while tmp.next and tmp.next.next:
  8.             cur = tmp.next.next
  9.             pre = tmp.next
  10.             tmp.next = cur
  11.             pre.next = cur.next
  12.             cur.next = pre
  13.             tmp = pre
  14.         return node.next
  16.         # 方法二：递归
  17.         if head == None or head.next == None:
  18.             return head
  19.         tmp = head.next
  20.         head.next = self.swapPairs(head.next.next)
  21.         tmp.next = head
  22.         return tmp

排序链表*

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。
输入：head = [4,2,1,3]
输出：[1,2,3,4]
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

  1. class Solution(object):
  2.     def sortList(self, head):
  3.         # 方法一：自顶向下归并排序
  4.         if not head or not head.next:
  5.             return head
  6.         pre = head
  7.         cur = head
  8.         # 用快慢指针分成两部分
  9.         while cur.next and cur.next.next:
  10.             pre = pre.next
  11.             cur = cur.next.next
  12.         # 找到左右部分, 把右边置空
  13.         mid = pre.next
  14.         pre.next = None
  15.         # 递归下去
  16.         # 此时head已经变为原来的一般，左半边
  17.         left = self.sortList(head)
  18.         # mid为右半边
  19.         right = self.sortList(mid)
  20.         # 合并
  21.         return self.merge(left, right)
  23.     def merge(self, left, right):
  24.         node = ListNode(0)
  25.         cur = node
  27.         while left and right:
  28.             if left.val < right.val:
  29.                 cur.next = left
  30.                 left = left.next
  31.                 cur = cur.next
  32.             else:
  33.                 cur.next = right
  34.                 right = right.next
  35.                 cur = cur.next
  36.         if left:
  37.             cur.next = left
  38.         if right:
  39.             cur.next = right
  40.         return node.next
  43.         # 方法二：自下向上归并排序，最优解，但是过程复杂
  44.         intv = 1
  46.         length = 0
  47.         high = head
  48.         # 计算链表长度
  49.         while high:
  50.             high = high.next
  51.             length += 1
  52.         node = ListNode(0)
  53.         node.next = head
  54.         # merge the list in different intv.
  55.         while intv < length:
  56.             mid, high = node, node.next
  57.             while high:
  58.                 # get the two merge head `h1`, `h2`
  59.                 h1, i = high, intv
  60.                 while i and high:
  61.                     high, i = high.next, i - 1
  62.                 if i:
  63.                     break  # no need to merge because the `h2` is None.
  64.                 h2, i = high, intv
  65.                 while i and high:
  66.                     high, i = high.next, i - 1
  67.                 c1, c2 = intv, intv - i  # the `c2`: length of `h2` can be small than the `intv`.
  68.                 # merge the `h1` and `h2`.
  69.                 while c1 and c2:
  70.                     if h1.val < h2.val:
  71.                         mid.next, h1, c1 = h1, h1.next, c1 - 1
  72.                     else:
  73.                         mid.next, h2, c2 = h2, h2.next, c2 - 1
  74.                     mid = mid.next
  75.                 mid.next = h1 if c1 else h2
  76.                 while c1 > 0 or c2 > 0:
  77.                     mid, c1, c2 = mid.next, c1 - 1, c2 - 1
  78.                 mid.next = high
  79.             intv *= 2
  80.         return node.next
  83.         # 方法三：都取出来排序再重新生成链表 
  84.         if head is None or head.next is None:
  85.             return head 
  87.         nums = []
  88.         cur = head
  89.         while cur:
  90.             nums.append(p.val)
  91.             cur = cur.next
  93.         nums.sort()
  94.         cur = head
  95.         while cur:
  96.             cur.val = nums.pop(0)
  97.             cur = cur.next
  98.         return head

K 个一组翻转链表*

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
输入：head = [1,2,3,4,5], k = 1
输出：[1,2,3,4,5]

  1. class Solution(object):
  2.     def reverseKGroup(self, head, k):
  3.         # 我们把 k 个数压入栈中，然后弹出来的顺序就是翻转的！
  4.         # 这里要注意几个问题：
  5.         # 第一，剩下的链表个数够不够 k 个（因为不够 k 个不用翻转）
  6.         # 第二，已经翻转的部分要与剩下链表连接起来。
  8.         # 方法一：栈
  9.         dummy = ListNode(0)
  10.         cur = dummy
  11.         while True:
  12.             count = k 
  13.             stack = []
  14.             tmp = head
  15.             while count and tmp:
  16.                 stack.append(tmp)
  17.                 tmp = tmp.next
  18.                 count -= 1
  19.             # 注意,目前tmp所在k+1位置
  20.             # 说明剩下的链表不够k个,跳出循环
  21.             if count : 
  22.                 cur.next = head
  23.                 break
  24.             # 翻转操作
  25.             while stack:
  26.                 cur.next = stack.pop()
  27.                 cur = cur.next
  28.             #与剩下链表连接起来 
  29.             cur.next = tmp
  30.             head = tmp
  31.         return dummy.next
  33.         # 方法二：最优解，尾插法
  34.         dummy = ListNode(0)
  35.         dummy.next = head
  36.         pre = dummy
  37.         tail = dummy
  38.         while True:
  39.             count = k
  40.             while count and tail:
  41.                 count -= 1
  42.                 tail = tail.next
  43.             if not tail: break
  44.             head = pre.next
  45.             while pre.next != tail:
  46.                 cur = pre.next # 获取下一个元素
  47.                 # pre与cur.next连接起来,此时cur(孤单)掉了出来
  48.                 pre.next = cur.next 
  49.                 cur.next = tail.next # 和剩余的链表连接起来
  50.                 tail.next = cur #插在tail后面
  51.             # 改变 pre tail 的值
  52.             pre = head 
  53.             tail = head
  54.         return dummy.next