Leetcode-链表（二）

24. 两两交换链表中的节点

https://leetcode-cn.com/problems/swap-nodes-in-pairs/

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:给定 1->2->3->4, 你应该返回 2->1->4->3.

题解

一：这类题目注意好用几个指针，是否要设置虚拟头加点，最后一个节点是否要手动将next置None，循环的条件是哪个指针。

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        before_head = ListNode(0)
        pre, cur, next = before_head, head, head.next

        while next:
            next_next = next.next
            pre.next = next
            next.next = cur
            cur.next = next_next
            pre = cur
            cur = next_next
            next = next_next.next if next_next else None
        return before_head.next

25. K 个一组翻转链表

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

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

示例：给你这个链表：1->2->3->4->5，当 k = 2 时，应当返回: 2->1->4->3->5，当 k = 3 时，应当返回: 3->2->1->4->5

说明：你的算法只能使用常数的额外空间。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

题解

一：起实与翻转链表那题极为相似，我们把每k个节点看作一个链表。假设目前在做底i次翻转，其中pre是第i-1次翻转后的链表的尾节点，他指向未做第i次翻转的小链表的头节点，start是第i次翻转的小链表的头节点，end是第i次翻转的小链表的尾节点，end_next是第i+1次翻转前的小链表的起始节点。下面是k=3的????。

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        def check(node, k):
        # 检查是否需要翻转，需要返回True，以及下一个单元的起始节点
        # 不需要返回False，此时我们并不关心第二个返回值是啥
            num = 0
            while node and num < k:
                num += 1
                node = node.next
            return num >= k, node
        
        before_head = ListNode(0)
        pre, pre.next = before_head, head

        while pre.next:
            flag, end_next = check(pre.next, k)
            if not flag:
                return before_head.next
            start, end = self._reverse(pre.next, k)
            pre.next = start
            end.next = end_next
            pre = end
        return before_head.next
 
    def _reverse(self, head, k):
    # 返回翻转后的头节点和尾节点
        pre, cur, num = None, head, 0

        while num < k:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
            num += 1
        return pre, head