24. Swap Nodes in Pairs

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

solution

• 可以一次移动两步，实现交替移动

• 当前pre和cur，交换的是 cur 和 cur.next

# 0(dummy) -> 1 -> 2 -> 3 -> 4

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1, next=head)
        pre = dummy
        cur = head

        while cur and cur.next:
            temp = cur.next.next  # 3
            cur.next.next = cur  # 2 -> 1
            pre.next = cur.next  # 0 -> 2
            cur.next = temp  # 1 -> 3

            pre = cur  # 向后移动 -1 > 1
            cur = cur.next  # 向后移动 1 > 3. 由于1已经挪到3前面了，实现按pair
        return dummy.next

时间复杂度：O() 空间复杂度：O()

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:        
        dummy = ListNode(next=head)

        cur = dummy
        while cur.next is not None and cur.next.next is not None:
            tmp1 = cur.next  # 被间隔的线隔开
            tmp2 = cur.next.next.next  # 被后面隔离

            cur.next = cur.next.next
            cur.next.next = tmp1
            cur.next.next.next = tmp2

            cur = cur.next.next  # 展开第一轮后可确定是两步
        return dummy.next

时间复杂度：O(n) 空间复杂度：O(1)

follow up

25. Reverse Nodes in k-Group

• 迭代法

# https://www.geeksforgeeks.org/reverse-a-linked-list-in-groups-of-given-size/

时间复杂度：O(n) 空间复杂度：O(1)

• 递归法

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return

        tail = head
        for _ in range(k):
            if not tail:
                return head
            tail = tail.next

        new_head = self.reverse(head, tail)
        head.next = self.reverseKGroup(tail, k)
        return new_head

    def reverse(self, head, tail):
        prev = None
        cur = head

        while cur != tail:
            temp = cur.next
            cur.next = prev
            prev = cur
            cur = temp
        return prev

时间复杂度：O(n) 空间复杂度：O(n)

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        # Check if we need to reverse the group
        curr = head
        for _ in range(k):
            if not curr: 
                return head
            curr = curr.next

        # Reverse the group (basic way to reverse linked list)
        prev = None
        curr = head
        for _ in range(k):
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        # After reverse, we know that `head` is the tail of the group.
		# And `curr` is the next pointer in original linked list order
        head.next = self.reverseKGroup(curr, k)
        return prev

• 栈的思路更直白一些

# https://zhuanlan.zhihu.com/p/674723050

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0)
        p = dummy
        while True:
            count = k
            stack = []
            tmp = head
            while count and tmp:
                stack.append(tmp)
                tmp = tmp.next
                count -= 1
            # 注意,目前tmp所在k+1位置
            # 说明剩下的链表不够k个,跳出循环
            if count :
                p.next = head
                break
            # 翻转操作
            while stack:
                p.next = stack.pop()
                p = p.next
            #与剩下链表连接起来
            p.next = tmp
            head = tmp
        return dummy.next