# 24. Swap Nodes in Pairs

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

## solution

* 可以一次移动两步，实现交替移动
* 当前pre和cur，交换的是 cur 和 cur.next

```python
# 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()

```python
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://leetcode.com/problems/reverse-nodes-in-k-group/)

* 迭代法

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

```

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

* 递归法

```python
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)

```python
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
```

* 栈的思路更直白一些

```python
# 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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://longxingtan.gitbook.io/mle-interview/01_leetcode/02_linked_list/24.-swap-nodes-in-pairs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.