【Day 8 】2021-12-19 - 24. 两两交换链表中的节点

[azl397985856]

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

入选理由

暂无

题目地址

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

前置知识

• 链表的基本知识

  题目描述

  
  给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

 

示例 1：

![image](https://assets.leetcode.com/uploads/2020/10/03/swap_ex1.jpg)

输入：head = [1,2,3,4] 输出：[2,1,4,3] 示例 2：

输入：head = [] 输出：[] 示例 3：

输入：head = [1] 输出：[1]  

提示：

链表中节点的数目在范围 [0, 100] 内 0 <= Node.val <= 100

[caohaha]

• 递归实现
• 时间复杂度O（n）
• 空间复杂度O（n）

class Solution { public: ListNode swapPairs(ListNode head) { //递归实现 if(head==NULL || head->next==NULL) return head; ListNode* node = head->next; head->next = swapPairs(node->next); node->next = head; return node; } };

[yan0327]

思路： 穿针引线 由于该题只涉及到两个节点之间的交换。因此可以利用pre.Next != nil&&pre.Next.Next != nil作为条件判断 即两个节点node1，node2分别表示pre的下一个，和pre的下下一个。 然后开始串，node1.Next = node.2.Next 保证顺序正确，pre.Next = node2 node2.Next = node1 形成一个闭环 PS:为了保证可以正常从表头获取整个链表，前面设置一个虚拟节点。

func swapPairs(head *ListNode) *ListNode {
    if head == nil{
        return nil
    }
    dummy := &ListNode{Next:head}
    pre := dummy
    for pre.Next != nil && pre.Next.Next != nil{
        node1 := pre.Next
        node2 := pre.Next.Next
        node1.Next = node2.Next
        pre.Next = node2
        node2.Next = node1
        pre = node1
    }
    return dummy.Next
}

时间复杂度：O（n） 空间复杂度：O（n）

[chakochako]

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        next = head.next
        head.next = self.swapPairs(next.next)
        next.next = head
        return next

[CodeWithIris]

Note (Iteration)

• Set a dummy head and point out to the head of the linked list.
• Draw the figure and then find the process involves 3 nodes: The previous node will point the second nodes, the first node will point out the second node's next node and finally the second node point out the first node.

Solution (C++)

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* tmp = dummy;
        while(tmp->next != nullptr && tmp->next->next != nullptr){
            ListNode* node1 = tmp->next;
            ListNode* node2 = tmp->next->next;
            tmp->next = node2;
            node1->next = node2->next;
            node2->next = node1;
            tmp = node1;
        }
        return dummy->next;
    }
};

Complexity

• T: O(n), n is the number of the nodes in linked list.
• S: O(1), only constant space

[wxj783428795]

思路

1. 两两交换节点，会形成闭环，所以要保存下下个节点作为当前节点的下个节点。
2. 也要保存当前节点的前一个节点，用于下两个节点与上两个节点之间的连接。
3. 要判断边界情况，比如链表长度为0和1的时候，直接返回head就行。

代码

var swapPairs = function (head) {
    let curr = head;
    if (!head || !head.next)
        return head;
    let answer = head.next;
    let prev = null;
    while (curr) {
        let next = curr.next;
        if (!next) {
            prev.next = curr;
            return answer
        }
        let nextnext = next.next;
        next.next = curr;
        curr.next = nextnext;
        if (prev) {
            prev.next = next;
        }
        prev = curr;
        curr = curr.next;
    }
    return answer
};

复杂度分析

复杂度分析不是很会，不一定对，如果有错，请指正。

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

[charlestang]

思路

递归：假设我们已经知道如何做这件事情。那么我们拿到一个链表，交换头两个节点的顺序，剩下的就调用自己完成就可以了。

边界：只有一个节点或者空链表，直接返回。

代码

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        p = head.next
        head.next = self.swapPairs(p.next)
        p.next = head
        return p

时间复杂度 O(n)

空间复杂度：O(n)

[Yutong-Dai]

思路

两两交换

代码

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        sentinel = ListNode(val=None, next=head)
        prev = sentinel
        curr_node = head
        # be careful about the edge case
        while curr_node and curr_node.next:
            next_node = curr_node.next
            curr_node.next = next_node.next
            next_node.next = curr_node
            prev.next = next_node
            prev = curr_node
            curr_node = curr_node.next
        # head is updated; do not return head
        return sentinel.next

复杂度

• 时间: O(n)
• 空间: O(n)

[feifan-bai]

思路

1. Recursion
2. If link list is 0 or 1, return head
3. save next node, pre node
4. swap the nodes 代码

   # Definition for singly-linked list.
   # class ListNode:
   #     def __init__(self, val=0, next=None):
   #         self.val = val
   #         self.next = next
   class Solution:
   def swapPairs(self, head: ListNode) -> ListNode:
       if not head or not head.next:
           return head
       newHead = head.next
       head.next = self.swapPairs(newHead.next)
       newHead.next = head
       return newHead

   复杂度分析

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

[q815101630]

两个两个得换

使用 dummy 和prev， prev指上一轮的前节点，dummy用来return

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        l = head
        prev = dummy = ListNode()
        if head and head.next:
            r = head.next
        else:
            return head

        rr = r.next

        while l and r:
            r.next = l
            l.next = rr
            prev.next = r

            prev = l
            l = rr
            if l and l.next:
                r = l.next
                rr = r.next
            else:
                r = None
        return dummy.next

时间 O(n) 空间 O(1)

[hwpanda]

var swapPairs = function(head) {

  let temp = new ListNode(0, null); // maintaining a temporary reference to sync with head
  temp.next = head;
  let current = temp;

  while (current.next && current.next.next) {
      let first_node = current.next;
      let second_node = current.next.next;

      // swap the nodes using the current
      first_node.next = second_node.next;
      current.next = second_node;
      current.next.next = first_node;
      current = current.next.next;
  }
  return temp.next; // return the head using the same temporary reference

};

[wangzehan123]

代码

• 语言支持：Java

Java Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) 
    {
        if(head==null||head.next==null)
            return head;
        ListNode myHead=new ListNode();
        myHead.next=head;
        ListNode p=myHead;
        while(p!=null&&p.next!=null&&p.next.next!=null)
        {
            var x=p.next;
            var y=p.next.next;
            x.next=y.next;
            y.next=x;
            p.next=y;
            p=x;
        }
        return myHead.next;
    }
}

[JuliaShiweiHuang]

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        strNum = ""
        for i in range(len(num)):
            strNum += str(num[i])
        numInt = int(strNum) + k
        lst = []
        if (numInt == 0):
            return [0]
        while numInt != 0:
            remainder = numInt % 10
            lst.append(remainder)
            numInt = numInt // 10
        lst_reverse = []
        j = len(lst) - 1
        while (j >= 0):
            lst_reverse.append(lst[j])
            j -= 1
        return lst_reverse

[davidcaoyh]

Add an sentinel before head

create an dummy point to sentinel

every iteration point dummy to head.next to link two sets

every iteration move both dummy and head to the next

when finishing, getting the expected result

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

    while head and head.next:
        dummy.next = head.next
        dummy = head.next
        head.next= head.next.next
        dummy.next = head
        dummy = dummy.next
        head= head.next

    return sentinel.next

[Menglin-l]

iterative approach

---

code:

class Solution {
    //   1   2   3   4   5
    //d  h 
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;
        ListNode cur = head;

        while (cur != null && cur.next != null) {

            ListNode t = cur.next;// initialize a temporary node
            // swapping
            cur.next = cur.next.next;
            t.next = cur;
            pre.next = t;
            // reinitialize the current node and pre node for the next swap
            pre = cur;
            cur = cur.next;
        }
        return dummy.next;
    }
}

---

complexity:

Time: O(N)

Space: O(1)

[zhangzz2015]

思路

• 比较直接，链表的操作注意避免环，以及利用虚头结点。因为头指针可能发生变化。交换涉及到4个结点。prevNode -> currentNode -> nextNode -> nextnextNode 变成 prevNode -> nextNode -> currentNode -> nextnextNode 。因此核心操作。 prevNode->next = nextNode nextNode->next = currentNode currentNode->next = nextnextNode. 然后更新 prevNode 和 currentNode。 时间复杂度为 O(N)，空间复杂度为 O(1)。

关键点

代码

• 语言支持：C++

C++ Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {

        ListNode tmpHead; 
        tmpHead.next = head; 

        ListNode* prev = & tmpHead; 
        ListNode* current = prev->next; 

        while(current && current->next)
        {
            ListNode* nextNext = current->next->next; 

            prev->next = current->next; 
            current->next->next = current; 

            current->next = nextNext; 

            prev = current; 
            current = nextNext; 
        }

        return tmpHead.next; 

    }
};

[yangziqi1998666]

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode newHead = head.next;
        head.next = swapPairs(head.next.next);
        newHead.next = head;
        return newHead;
    }
}

[yijing-wu]

思路

recursion

代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}

复杂度分析

• Time Complexitty = O(N)
• Space Complexitty = O(N)

[li65943930]

var swapPairs = function (head) { if (!head || !head.next) return head; let nextNode = head.next; head.next = swapPairs(nextNode.next); nextNode.next = head; return nextNode; };

[laofuWF]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: return head

        dummy = ListNode(-1)
        dummy.next = head.next

        next_batch = head.next.next
        head.next.next = head

        head.next = self.swapPairs(next_batch)

        return dummy.next

[rzhao010]

Thoughts

Use dummyhead point to head, another pointer pre to track the current node

Code

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        while (pre.next != null && pre.next.next != null) {
            ListNode start = pre.next;
            ListNode end = pre.next.next;
            pre.next = end;
            start.next = end.next;
            end.next = start;
            pre = start;
        }
        return dummy.next;
    }

Complexity

• Time: O(n)
• Space: O(1)

[xj-yan]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = pointer = ListNode(0, head)
        while pointer:
            node = pointer
            cnt = 0
            while cnt < 2 and node:
                cnt += 1
                node = node.next
            if not node: break
            prev, curt, nxt = None, pointer.next, None
            for i in range(2):
                nxt = curt.next
                curt.next = prev
                prev = curt
                curt = nxt
            tail = pointer.next
            tail.next = curt
            pointer.next = prev
            pointer = tail
        return dummy.next

Time Complexity: O(n), Space Complexity: O(1)

[tongxw]

思路

每次反转2个节点，定义四个指针，分别指向这两个节点，它们前面的那个节点和它们后面的那个节点。根据题意修改next指针

代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode prev = dummy;
        while (prev != null && prev.next != null) {
            prev = swapNextPair(prev);
        }

        return dummy.next;
    }

    private ListNode swapNextPair(ListNode prev) {
        if (prev == null || prev.next == null || prev.next.next == null) {
            return null;
        }

        // 四个指针：指向这两个节点，它们前面的节点和它们后面的节点
        ListNode p1 = prev.next;
        ListNode p2 = p1.next;
        ListNode next = p2.next;

        prev.next  = p2;
        p2.next = p1;
        p1.next = next;

        // 最后返回下一组两个节点的前面的节点
        return p1;
    }
}

TC: O(n) SC: O(1)

[Yachen-Guo]

采用递归的方式，时间复杂度O(N)

base case: 只有一个节点/节点是null，return node itself

recursive case: head节点接上递归的结果（recur(head.next.next)）head.next接上head 实现反转

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        return swapPairRec(head);
    }

    private ListNode swapPairRec(ListNode node){
        if(node == null || node.next == null) return node;
        ListNode nodeNext = node.next;
        node.next = swapPairRec(node.next.next);
        nodeNext.next = node;
        return nodeNext;
    }
}

[ginnydyy]

Problem

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

Note

• Sentinel nodes
• Group every two nodes between two sentinel nodes

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        // set the dummy for return val
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // sHead -> start -> end -> sTail
        ListNode sHead = dummy;
        ListNode start, end, sTail;

        while(sHead.next != null && sHead.next.next != null){ // start and end not null
            // set up nodes
            start = sHead.next;
            end = start.next;
            sTail = end.next;

            // reverse
            end.next = start;
            sHead.next = end;
            start.next = sTail;

            // update for next loop
            sHead = start;
        }

        return dummy.next;
    }
}

Complexity

• T: O(n) n is the number of nodes in the list
• S: O(1)

[wenjialu]

thought

Recursion

code

class Solution: def swapPairs(self, head: ListNode) -> ListNode: if not head or not head.next: return head node = head next_node = node.next node.next = self.swapPairs(next_node.next) # 不是在主函数里面接下一个，而是直接在这里就把之后翻转的给接上了。 next_node.next = node

    return next_node    

complexity

Time: O(n) Space: O(n)

[zhangyalei1026]

Main idea

dummy node - pre first - head second - head.next

Code

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        dummy = ListNode(-1)
        pre = dummy
        first = head
        second = head.next

        while first and second:
            first.next = second.next
            second.next = first
            pre.next = second
            pre = first
            first = first.next
            second = first.next if first else None
        return dummy.next

Complexity

Time complexity: O(n) Space complexity: O(1)

[CoreJa]

思路

用一个空节点来作为头，省掉头的edge case。然后两个指针换来换去就行了

python

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        p = ListNode()
        p.next = head
        head = p
        while (q := p.next) and q.next:
            p.next = q.next
            q.next = q.next.next
            p.next.next = q
            p = p.next.next
        return head.next

[zwx0641]

class Solution { public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) return head; ListNode next = head.next; head.next = swapPairs(next.next); next.next = head; return next; } }

[yingliucreates]

const swapPairs = function(head) {
    if(!head || !head.next) return head;
    const v1 = head, v2 = head.next, v3 = v2.next;
    v2.next = v1;
    v1.next = swapPairs(v3);
    return v2;
};

[XinnXuu]

Notes

注意改变节点时的次序

Code (Java)

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        while(cur.next != null && cur.next.next != null) {
            ListNode node1 = cur.next;
            ListNode node2 = cur.next.next;
            cur.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            cur = node1;
        }
        return dummy.next;
    }
}

Complexity

• Time: O(N)
• Space: O(1)

[Bochengwan]

思路

通过recursive，每次取前两个node

代码

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:

        if not head or not head.next:
            return head
        first,second = head, head.next
        first.next = self.swapPairs(second.next)
        second.next =first
        return second

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(N)

[CodingProgrammer]

思路

递归，递归函数的返回值是当前两个节点反转后的头，入参数为原来链表中两个节点的头。首先两个节点完成反转，记录新的头和新的尾，新的尾指向下一对的头（用递归生成），返回当前这一段的新头

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // 到达尾部，返回
        if (head == null || head.next == null)
            return head;

        ListNode headNew = head.next;
        ListNode next = headNew.next;
        headNew.next = head;
        head.next = swapPairs(next);

        return headNew;
    }
}

复杂度

• Time: O (N)
• Space: O(1)

[Alexno1no2]

思路： 假设需要交换的两个点为 head 和 next，head 连接后面交换完成的子链表，next 连接 head，完成交换 当head 为空或者 next 为空，即当前无节点或者只有一个节点，不再进行交换

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        next = head.next
        head.next = self.swapPairs(next.next)
        next.next = head
        return next

[nonevsnull]

思路

• 思路与解法

• 做过很多遍了，主要是要凝练写法，思路要清晰且容易表达，变量设置要合理

代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode pre = dummy;
        ListNode cur = head;
        if(head == null) return head;
        ListNode next = cur.next;

        while(next != null) {
            ListNode nextCur = next.next;
            next.next = cur;
            cur.next = nextCur;
            pre.next = next;

            pre = cur;
            cur = nextCur;
            next = null;
            if(cur != null && cur.next != null) next = cur.next;
        }

        return dummy.next;
    }
}

复杂度

time: O(N) space: O(1)

[spacker-343]

思路

找到起始节点，和终止节点就行了

代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode b=head;
        // i<k就是k个一组翻转链表啦
        for(int i=0; i<2; i++){
            if(b==null){
                return head;
            }
            b=b.next;
        }
        // 翻转后返回的就是头结点
        ListNode res=reverse(head, b);
        // head变为尾结点了
        head.next=swapPairs(b);
        return res;
    }

    // 翻转[a, b)区间
    private ListNode reverse(ListNode a, ListNode b){
        if(a==b){
            return a;
        }
        if(a.next==b){
            return a;
        }
        ListNode head=reverse(a.next, b);
        a.next.next=a;
        a.next=null;
        return head;
    } 
}

复杂度

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

[ZhangNN2018]

思路

• 回溯

复杂度

• 时间复杂度: O(N)；
• 空间复杂度: O(1)。

代码

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

[JudyZhou95]

思路

iterative 解法：需要prev, first, second 三个指针。prev：用于上两个node和下两个node进行连接。first和second是一组内需要交换的两个node。先用这三个指针将first和second交换，first就成新的prev连接之后的一组node。 recursive解法：需要两个指针first, second。 second之后的node放入recursive function。之后进行轮换，first之后接recursive function返回的值，second之后接first，最后返回second。

代码

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        dummy = ListNode(-1)
        dummy.next = head

        prev_node = dummy

        while head and head.next:
            first_node = head
            second_node = head.next

            prev_node.next = second_node
            first_node.next = second_node.next
            second_node.next = first_node

            prev_node = first_node
            head = first_node.next

        return dummy.next

    """
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        first_node = head
        second_node = head.next

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

        return second_node
    """

复杂度

Time Complexity: O(N) Space Complexity: O(1)

[Alyenor]

思路 创建虚拟头结点 dummy，指向 head：dummy -> head -> 2 -> 3 -> 4 -> 5，交换指针： dummy -> 2 2 -> head head -> 3 完成后，链表变成 dummy -> 2 -> 1 -> 3 -> 4 -> 5，将指向 dummy 的指针往后移动继续之前的操作，直到结尾。

代码 function swapPairs(head: ListNode | null): ListNode | null { if (!head) return null; const dummy = new ListNode(-1); dummy.next = head; let temp = dummy; while (temp.next && temp.next.next) { const a = temp.next, b = temp.next.next; temp.next = b; a.next = b.next; b.next = a; temp = a; } return dummy.next; } 分析 时间复杂度：O(n) 空间复杂度：O(1)

[pangjiadai]

Python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head: return head
        dummy = ListNode(-1)
        dummy.next = head

        prev = dummy
        A = head

        while A and A.next:
            B = A.next
            nextB = B.next

            prev.next = B
            B.next = A 
            A.next = nextB

            prev = A
            A = nextB

        return dummy.next

复杂度

• time complexity: O(n)
• space complexity: O(1)

[Myleswork]

思路

我想试试递归，迭代还是很好理解的。

就是最简单的思路，奇偶相邻两个节点进行swap，这不是最重要的。重要的是替换后对应节点之间的连接需要更新。

比如[1,2,3,4]，如果仅仅只是swap，那么在[3,4]两个节点swap之后，3就会被孤立出来，单独指向4，没有前序节点。那么解决方法就是在[1,2]两个节点swap结束之后，事先让节点“1”(这里的1指的是值为1的节点)指向节点“4”，这样就能解决链路断连的情况。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void swap(ListNode* node1,ListNode* node2){
         ListNode* temp = node2->next;
         node2->next = node1;
         node1->next = temp;
    }
    ListNode* swapPairs(ListNode* head) {
        if(!head || head->next == nullptr) return head;
        ListNode* headreal = head->next;   //记录最后需要返回的首节点
        ListNode* node1 = head;
        ListNode* node2 = head->next;
        while(true){
            swap(node1,node2);
            ListNode* temp = node1;
            node1 = node1->next;
            if(!node1) break; 
            node2 = node1->next;
            if(!node2) break;
            temp->next = node2;
        }
        return headreal;

    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

[ray-hr]

思路

可以通过递归的方式实现两两交换链表中的节点。

递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。

如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。

用 head 表示原始链表的头节点，新的链表的第二个节点，用 newHead 表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是 newHead.next。令 head.next = swapPairs(newHead.next)，表示将其余节点进行两两交换，交换后的新的头节点为 head 的下一个节点。然后令 newHead.next = head，即完成了所有节点的交换。最后返回新的链表的头节点 newHead

代码

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        newHead = head.next
        head.next = self.swapPairs(newHead.next)
        newHead.next = head
        return newHead

[zwmanman]

思路

create dummy node

代码

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

        dummy = ListNode()
        dummy.next = head.next
        pre = dummy

        while head and head.next:
            nextNode = head.next
            n_next = nextNode.next

            nextNode.next = head
            head.next = n_next
            pre.next = nextNode

            pre = head
            head = n_next

        return dummy.next

复杂度分析

• 时间复杂度：O(N)，其中 N 为List长度。
• 空间复杂度：O(1)

[junbuer]

思路

创建哑节点dummy，设置temp指针，初始指向dummy。将temp指针后的两个节点node1和node2交换，然后更新temp指针指向交换后的第二个节点即node1。直到temp后的任一节点为NULL

代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        temp = dummy
        while temp.next and temp.next.next:
            node1 = temp.next
            node2 = node.next
            temp.next = node2
            node1.next = node2.next
            node2.next = node1
            temp = node1
        return dummy.next

复杂度分析

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

[Toms-BigData]

【Day 8】24. 两两交换链表中的节点

思路

设置一个头节点，根据链表长度为单数或者双数确定终止条件，遍历链表两两交换

Golang代码

func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil{
        return head
    }
    num := 1
    new_head := ListNode{0,head}
    a_point := &new_head
    b_point := head
    c_point := head.Next
    for c_point != nil{
        c_point = c_point.Next
        num++
    }
    c_point = head.Next
    b_point.Next = c_point.Next
    a_point.Next = c_point
    c_point.Next = b_point
    if num %2 == 0{
        for b_point.Next != nil{
            a_point,b_point,c_point = exchangeListNode(a_point, b_point, c_point)
        }
    }else {
        for b_point.Next.Next != nil{
            a_point,b_point,c_point = exchangeListNode(a_point, b_point, c_point)
        }
    }
    return new_head.Next
}
func exchangeListNode(a_point *ListNode, b_point *ListNode, c_point *ListNode) (*ListNode, *ListNode, *ListNode) {
    a_point = a_point.Next.Next
    b_point = a_point.Next
    c_point = b_point.Next
    b_point.Next = c_point.Next
    a_point.Next = c_point
    c_point.Next = b_point
    return a_point,b_point,c_point
}

复杂度

时间:O(n) 空间:O(1)

[ZacheryCao]

Idea:

Relink the second node's next to first node, and first node's next to next second node. Need an extra pointer to record previous first node at each iteration

Code

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        new_head = head.next
        pre_tail = None
        while head:
            first = head
            second = None
            if head.next:
                second = head.next
            if second:
                first.next = second.next
                second.next = first
            else:
                break
            if pre_tail:
                pre_tail.next = second
            pre_tail = first
            head = first.next
        return new_head

Complexity:

Time: O(N) Space: O(1)

[sujit197]

思路

递归，将head.next指针指向swap后的节点，head.next.next指向head

代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode newNode = head.next;
        head.next = swapPairs(newNode.next);
        newNode.next = head;
        return newNode;

    }
}

复杂度

时间复杂度： O（N）

空间复杂度： O（1）

[devosend]

思路

迭代

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:

        if not head or not head.next:
            return head

        cur = head
        head = cur.next
        while cur and cur.next:
            tmp = cur.next.next
            cur.next.next = cur
            if tmp and tmp.next:
                cur.next = tmp.next
            else:
                cur.next = tmp
            cur = tmp

        return head

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(1)

[simbafl]

--python

1. 递归
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        start = head.next
        head.next = self.swapPairs(start.next)
        start.next = head
        return start

2. 迭代
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        start = head.next
        dummy = ListNode(-1)
        dummy.next = head
        while dummy.next and dummy.next.next:
            p = dummy.next
            q = dummy.next.next
            p.next = q.next
            dummy.next = q
            q.next = p 
            dummy = dummy.next.next
        return start

时间复杂度: O(n) 空间复杂度: O(1), 但递归比迭代多了栈的使用

[Aobasyp]

思路 迭代 原始链表为 preA -> A -> B -> nextB，我们需要改为 preA -> B -> A -> nextB， 接下来用同样的逻辑交换 nextB 以及 nextB 的下一个元素。

class Solution { public ListNode swapPairs(ListNode head) { if(head == null || head.next == null) return head; ListNode preNode = new ListNode(-1, head), res; preNode.next = head; res = head.next; ListNode firstNode = head, secondNode, nextNode; while(firstNode != null && firstNode.next != null){ secondNode = firstNode.next; nextNode = secondNode.next;

        firstNode.next = nextNode;
        secondNode.next = firstNode;
        preNode.next = secondNode;

        preNode = firstNode;
        firstNode = nextNode;
    }
    return res;
}

}

时间复杂度：所有节点只遍历一遍，时间复杂度为O(N)O(N) 空间复杂度：未使用额外的空间，空间复杂度O(1)O(1)

[baddate]

题目

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

思路

链表迭代，构造一个临时节点nhead指向head ，nhead作为最终结果的指针不动，用一个新指针prev指向nhead用来执行交换操作

特殊情况：链表大小为0或1的时候直接返回head

代码

/* 迭代思路 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* nhead = new ListNode(-1);
        nhead->next = head;
        ListNode* prev = nhead;

        while(head != nullptr && head->next != nullptr)
        {
            prev->next = head->next;
            head->next = prev->next->next;
            prev->next->next = head;
            prev = head;
            head = head->next;
        }
        return nhead->next;
    }
};

复杂度分析

• 时间复杂度：O(N)，N为链表大小
• 空间复杂度：O(1)，构造了一个临时节点，其余均在原链表上操作