【Day 8 】2023-02-21 - 24. 两两交换链表中的节点

[azl397985856]

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

入选理由

暂无

题目地址

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

前置知识

• 链表的基本知识

  题目描述

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

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

 

示例 1：

![image](https://p.ipic.vip/r1afvu.jpg)

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

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

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

提示：

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

[Meisgithub]

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
        {
            return head;
        }
        ListNode* newHead = head->next;
        ListNode* nextHead = head->next->next;
        newHead->next = head;
        head->next = swapPairs(nextHead);
        return newHead;
    }
};

[839781960]

思路：设置虚拟listnode用来用来做交换的中介量

public class _24两两交换链表中的节点 {
    public ListNote01 swapPairs(ListNote01 head) {
        ListNote01 vl = new ListNote01();
        vl.next = head;

        ListNote01 p = vl;

        while (p.next!=null&&p.next.next!=null){
            ListNote01 first = p.next;
            ListNote01 second = p.next.next;

            first.next = second.next;
            second.next = first;
            p.next=second;

            p=p.next.next;
        }
        return vl.next;
    }
}

[Manwzy]

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

[linlizzz]

思路

先把链表首尾相连，再找到位置断开循环

代码

class Solution(object):
    def rotateRight(self, head, k):
        if head is None or head.next is None: return head
        start, end, len = head, None, 0
        while head:
            end = head
            head = head.next
            len += 1
        end.next = start
        pos = len - k % len
        while pos > 1:
            start = start.next
            pos -= 1
        ret = start.next
        start.next = None
        return ret

[JadeLiu13]

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]: res = ListNode(next=head) pre = res

剩1或0，则遍历结束

    while pre.next and pre.next.next:
        cur = pre.next
        post = pre.next.next            
        # pre，cur，post对应最左，中间的，最右边的节点
        cur.next = post.next
        post.next = cur
        pre.next = post

        pre = pre.next.next
    return res.next

[JiangyanLiNEU]

Idea

• remove and rebuild the link until there is less than 2 nodes left

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

• Time = O(N) N=length of the listed list
• Space = O(1)

[Ryanbaiyansong]

··· 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 pre = dummy cur = head

    while cur and cur.next:
        sec = cur.next
        tmp = cur.next.next
        cur.next.next = cur 
        cur.next = tmp 
        pre.next = sec 
        pre = cur 
        cur = cur.next 

    return dummy.next

··· O(N) O(1)

[hatoriMain]

/**

• 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) { ListNode dummy = new ListNode(5); dummy.next = head; ListNode preNode = dummy; ListNode firstNode = head; ListNode secondNode; ListNode postNode; while(firstNode != null && firstNode.next != null) { secondNode = firstNode.next; postNode = secondNode.next;

      preNode.next = secondNode;
  
      firstNode.next = postNode;
      secondNode.next = firstNode;
      preNode = firstNode;
      firstNode = postNode;
  
  }
  return dummy.next;

  } }

[zzhilin]

思路

use a dummy head and prev to save the node before swapping, then swap the two nodes on the go iteratively.

1. setup dummy head
2. swap first node and second node
3. move the pointers by updating head node and prev

代码

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dh = ListNode(-1)
        dh.next = head
        prev = dh

        while head != None and head.next != None:
            first = head
            second = head.next

            prev.next = second
            first.next = second.next
            second.next = first

            prev = first
            head = first.next

        return dh.next

复杂度分析 time: O(n), iterate over the linkedlist with n nodes space: O(1)

[Yufanzh]

two approaches: recursive and iteratively.

# 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]:
        # typical linked list problem: recursive & iterative
        # method 1. recursive:
        # p1 --> p2 --> rest
        # p2 --> p1 --> rest
        # # edge case
        # while not head or not head.next:
        #     return head
        # p1 = head
        # p2 = head.next
        # p1.next = self.swapPairs(p2.next)
        # p2.next = p1
        # return p2

        # method 2. iteratively
        # keep point1, 2 to move and swap p1 --> p2 --> next
        while not head or not head.next:
            return head
        dummy = ListNode(0)
        dummy.next = head
        p0 = dummy
        while p0 and p0.next and p0.next.next:
            p1 = p0.next
            p2 = p0.next.next
            # start to swap
            p1.next = p2.next
            p2.next = p1
            p0.next = p2
            p0 = p1
        return dummy.next

[dinjufen]

思路：递归，递归首先要知道最小步骤是什么，在这里最小步骤是两两交换节点，然后交换后的第二个节点指向下一次递归的返回值

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* next = head->next;
        head->next = swapPairs(next->next);
        next->next = head;
        return next;
    }
};

[954545647]

/**

• Definition for singly-linked list.
• function ListNode(val, next) {
• this.val = (val===undefined ? 0 : val)
• this.next = (next===undefined ? null : next)
• } */ /**
• @param {ListNode} head
• @return {ListNode} */ var swapPairs = function (head) { if (!head || !head.next) return head; let dummy = new ListNode(0); dummy.next = head; // preHead let help = head; let res = head.next; // 返回的结果 while (help && help.next) { let nextNode = help.next; let nnNode = nextNode.next; help.next = nnNode; nextNode.next = help; dummy.next = nextNode; dummy = help; help = nnNode; } return res; };

[bookyue]

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

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

        var next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }

[hshen202108]

题目地址(24. 两两交换链表中的节点)

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

题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：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;
        }
        //假设链表是 1->2->3->4
        //这句就先保存节点2
        ListNode tmp = head.next;
        //继续递归，处理节点3->4
        //当递归结束返回后，就变成了4->3
        //于是head节点就指向了4，变成1->4->3
        head.next = swapPairs(tmp.next);
        //将2节点指向1
        tmp.next = head;
        return tmp;
    }

}

复杂度分析

令 n 为链表长度。

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

[Elon-Lau]

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

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

    var next = head.next;
    head.next = swapPairs(next.next);
    next.next = head;
    return next;
}

[KangQinSen]

思路

定义一个prev， 一个current（current 是 prev.next) 。保持prev不变，交换current和current.next 。 然后prev指向current(即交换后的next)

关键点

head指针会变化的题，定义dummy。 dummy也是最开始的prev

代码

• 语言支持：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 dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode current= dummy.next; 
        ListNode nextNode= null;
        while(current != null && current.next != null){
          nextNode = current.next;
          prev.next = nextNode; 
          current.next = nextNode.next;
          nextNode.next = current;

          prev = current;
          current = prev.next ; 
        }

        return dummy.next;
    }
}

复杂度分析

令 n 为数组长度。

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

[zpbc007]

解法 1

递归

思路

第一个节点 -> 第二个节点

1. 用临时变量存储第二个节点
2. 让第一个节点指向交换后的第二个节点的下一个节点（递归）
3. 第二个节点指向第一个节点

代码

function swapPairs(head: ListNode | null): ListNode | null {
    // 头结点不存在 | 只有一个节点
    if (!head || !head.next) {
        return head
    }

    let tmp: ListNode | null = null

    tmp = head.next
    head.next = swapPairs(head.next.next)
    tmp.next = head

    return tmp
}

复杂度

• 空间复杂度：O(1)
• 时间复杂度：O(N) 整个链表遍历一遍

解法 2

循环

思路

1. pre 存储当前头结点的上一个节点
2. 正常交换节点
3. 如果有 pre 更新下 pre 的指向
4. 头节点移动到下个位置

代码

function swapPairs(head: ListNode | null): ListNode | null {
    if (!head || !head.next) {
        return head
    }
    let tmp: ListNode | null = null
    let newHead: ListNode | null = null
    let pre: ListNode | null = null

    while (head && head.next) {
        // 两两交换
        tmp = head.next
        head.next = head.next.next
        tmp.next = head

        if (pre) {
            pre.next = tmp
        }
        // 移动到下个位置
        head = tmp.next.next
        pre = tmp.next
        if (!newHead) {
            newHead = tmp
        }
    }

    return newHead
}

复杂度

• 空间复杂度：O(1)
• 时间复杂度：O(N) 整个链表遍历一遍

[NorthSeacoder]

代码(递归)

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    if (!head || !head.next) return head;
    const next = head.next;
    //获取交换后的链表
    head.next = swapPairs(next.next);
    //交换当前节点
    next.next = head;
    return next
};

复杂度

• TC:O(n);
• SC:O(n)

代码(迭代)

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    if (!head || !head.next) return head;
    //虚拟头结点
    const newHead = new ListNode(0, head);
    let point = newHead;
    while (point.next && point.next.next) {
        const pre = point.next;
        const post = point.next.next;
        //指针指向 post,post 为首位;
        point.next = post;
        //pre 指向后续节点,pre 此时为第二位;
        pre.next = post.next;
        //post 指向 pre,交换完成
        post.next = pre;
        //指针移至 pre 进入下一步迭代
        point = pre;
    }
    return newHead.next;
};

复杂度

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

[RestlessBreeze]

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) {
        if (!head || !head -> next)
            return head;
        ListNode* newHead = swapPairs(head -> next -> next);
        ListNode* p = head -> next;
        head -> next = newHead;
        p -> next = head;
        return p;
    }
};

[duke-github]

思路

迭代 每次向后遍历两位 交换他们的位置

复杂度

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

代码

class Solution {
    public static ListNode swapPairs(ListNode head) {
        ListNode temp = new ListNode(0,head);
        ListNode ans = temp;
        while(head!=null&&head.next!=null){
            temp.next = temp.next.next;
            head.next = head.next.next;
            temp.next.next = head;
            head = head.next;
            temp = temp.next.next;
        }
        return ans.next;
    }
}

[csthaha]

思路：

• 递归进行两两交换即可。

  复杂度：

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

    代码：

    
    /**

• Definition for singly-linked list.
• function ListNode(val, next) {
• this.val = (val===undefined ? 0 : val)
• this.next = (next===undefined ? null : next)
• } */ /**
• @param {ListNode} head
• @return {ListNode} */ var swapPairs = function(head) { var cb = head => { if(!head || !head.next) return head; let cur; cur = head.next; next = cur.next; cur.next = head; head.next = null; head = cur; if(next) { head.next.next = cb(next) } return head; } return cb(head); };

[wangqianqian202301]

思路

使用两个变量， 一个pre, 一个left结点实现两两逆转

代码

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

        pre = ListNode()
        pre.next = head
        left = head
        head = pre
        while left is not None and left.next is not None:
            pre.next = left.next
            left.next = left.next.next
            pre.next.next = left
            pre = left
            left = left.next
        pre = None

        return head.next

复杂度

O(n) O(1)

[suukii]

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

  function swapPairs(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head;
  const rest = swapPairs(head.next.next);
  const [first, second] = [head, head.next];
  first.next = rest;
  second.next = first;
  return second;
  };

[Elsa-zhang]

# 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:
            return head
        dummyhead = ListNode()
        dummyhead.next = head
        temp = dummyhead

        while temp.next and temp.next.next:
            node1 = temp.next
            node2 = temp.next.next

            temp.next = node2
            node1.next = node2.next
            node2.next = node1

            temp = node1

        return dummyhead.next

[yan-jie]

var swapPairs = function(head) {
    if(head === null || head.next === null){
        return head;
    }
    const newHead = head.next;
    head.next = swapPairs(head.next.next);
    newHead.next = head;
    return newHead;
};

[Fuku-L]

思路

1. 新增一个虚拟头节点，以保持交换操作的一致性。
2. 循环条件为 cur.next != null && cur.next.next != null

代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode cur = pre;
        while (cur.next != null && cur.next.next!=null){
            ListNode tmp = cur.next;
            cur.next = tmp.next;
            tmp.next = cur.next.next;
            cur.next.next = tmp;
            cur = tmp;
        }
        return pre.next;
    }
}
/**
 * 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; }
 * }
 */

复杂度分析

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

[airwalkers]

public ListNode swapPairs(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode pre = new ListNode();
        pre.next = head;
        ListNode p = pre, q = p.next;
        while (q != null && q.next != null) {
            ListNode r = q.next;
            ListNode next = r.next;
            r.next = q;
            q.next = next;
            p.next = r;
            p = q;
            q = next;
        }
        return pre.next;
    }

[jmaStella]

思路

1. 借助了一些hint，提示用recursion。
2. new listNode fakehead 帮助返回new head。
3. Base Case： curr==null || curr.next ==null
4. Recursion: parent -> swap1 -> swap2 -> temp 变为 parent -> swap2 -> swap1 -> temp

代码

class Solution {
    public ListNode swapPairs(ListNode head) {

        ListNode fakeHead = new ListNode();
        fakeHead.next = head;
        helper(fakeHead, head);
        return fakeHead.next;
    }
    public void helper(ListNode parent, ListNode swap1){

        if(swap1 == null || swap1.next == null){
            return;
        }
        ListNode swap2 = swap1.next;
        ListNode temp = swap2.next;
        swap2.next = swap1;
        swap1.next = temp;
        parent.next = swap2;

        helper(swap1, swap1.next);
    }

}

复杂度

时间：O(N) 空间： O(1)

[kofzhang]

思路

模拟

复杂度

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

代码

# 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,head)
        left = dummy
        cur = head
        right = head.next
        while cur and cur.next:
            left.next = right
            cur.next = right.next
            right.next = cur

            left = cur
            cur = cur.next
            if cur and cur.next:
                right = cur.next
        return dummy.next

[X1AOX1A]

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

题目

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

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

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

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

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

思路1

• 观察规律，如图所示
• 首先排除没有任何 node 或者只有一个 node 的链表
• 对于起码有两个 node 的链表，轮流记录 first node 和 second node，反复进行 step 1～2 操作
• 直到没有 new_first（偶数链表）或者没有 new_first.next（奇数链表），进行 step 3 操作

代码1

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        """
        用递归实现链表相邻互换：
        第一个节点的 next 是第三、第四个节点交换的结果，第二个节点的 next 是第一个节点；
        第三个节点的 next 是第五、第六个节点交换的结果，第四个节点的 next 是第三个节点；
        以此类推
        :param ListNode head
        :return ListNode
        """
        if not head or not head.next:
            return head

        first = head
        second = head.next
        new_head = second

        while True:
            new_first = second.next
            # step 1. link `sencod` to `first`
            second.next = first
            # step 3, return `new_head` when come to the end
            if not new_first or not new_first.next:
                first.next = new_first
                return new_head
            # step 2. link `first` to `new_second`
            else:                
                first.next = new_first.next                
            # move forward, repeat step 1~2 until step 3
            first = new_first
            second = new_first.next

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

思路2：递归

• 用递归实现链表相邻互换：
  • 第一个节点的 next 是第三、第四个节点交换的结果，
    • 第二个节点的 next 是第一个节点；
  • 第三个节点的 next 是第五、第六个节点交换的结果，
    • 第四个节点的 next 是第三个节点；
• 以此类推

代码2

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        """
        用递归实现链表相邻互换：
        第一个节点的 next 是第三、第四个节点交换的结果，第二个节点的 next 是第一个节点；
        第三个节点的 next 是第五、第六个节点交换的结果，第四个节点的 next 是第三个节点；
        以此类推
        :param ListNode head
        :return ListNode
        """
        # 如果为 None 或 next 为 None，则直接返回
        if not head or not head.next:
            return head

        _next = head.next                      # 第二个节点
        head.next = self.swapPairs(_next.next) # 第一个节点的 next 是：第三、第四个节点交换的结果
        _next.next = head                      # 第二个节点的 next 是：第一个节点
        return _next

• 时间复杂度：O(N)，所有节点只遍历一遍
• 空间复杂度：O(1)

[Hughlin07]

class Solution {

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

    ListNode temp = head.next;
    head.next = swapPairs(temp.next);
    temp.next = head;
    return temp;
}

}

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

[harperz24]

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

        pre = dummy
        first = head

        while first and first.next:
            second = first.next 
            suc = second.next

            # Swap the two nodes
            pre.next = second
            second.next = first
            first.next = suc

            # Move prev pointer to first node in swapped pair
            pre = first
            first = suc

        return dummy.next

        # iteration 
        # time: O(n)
        # space: O(1)

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

        first = head
        second = head.next

        first.next = self.swapPairs(second.next)
        second.next = first

        return second

        # recursion
        # time: O(n)
        # space: O(n)

[Size-of]

/**

• Definition for singly-linked list.
• function ListNode(val, next) {
• this.val = (val===undefined ? 0 : val)
• this.next = (next===undefined ? null : next)
• } */ /**
• @param {ListNode} head

• @return {ListNode} */ var swapPairs = function(head) { const pre = new ListNode(-1) pre.next = head let now = pre

  while (now.next !== null && now.next.next !== null) { let start = now.next let end = now.next.next

  now.next = end
  start.next = end.next
  end.next = start
  now = start

  }

  return pre.next };

[AstrKing]

思路

采用递归的思想，两个两个一组，先对前面两个进行翻转，再把剩下的依次进行翻转

代码

class Solution {
    // 定义：输入以 head 开头的单链表，将这个单链表中的每两个元素翻转，
    // 返回翻转后的链表头结点
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode first = head;
        ListNode second = head.next;
        ListNode others = head.next.next;
        // 先把前两个元素翻转
        second.next = first;
        // 利用递归定义，将剩下的链表节点两两翻转，接到后面
        first.next = swapPairs(others);
        // 现在整个链表都成功翻转了，返回新的头结点
        return second;

    }
}

复杂度分析

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

[sye9286]

思路

如果 head 为空或者只有一个点，则不用交换直接返回，有两个点的，用递归的方式交换两个点。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    if (head === null || head.next === null)
        return head;

    let newHead = head.next;
    head.next = swapPairs(newHead.next)
    newHead.next = head;

    return newHead;
};

复杂度分析

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

[Zoeyzyzyzy]

class Solution {
   public ListNode swapPairs(ListNode head) {
      ListNode node = new ListNode(0);
        node.next = head;
        ListNode ptr = head;
        while (ptr!= null && ptr.next != null) {
            ListNode newNode = ptr.next;
            ptr.next = newNode.next;
            newNode.next = ptr;
            ptr = ptr.next;
        }
        return node.next;
    }
}

[LIMBO42]

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr) return head;
        if(head->next == nullptr) return head;
        ListNode* cur = head;
        ListNode* pre = nullptr;
        ListNode* ans = nullptr;
        while(cur) {
            ListNode* next = cur->next;
            if(ans == nullptr) ans = next;
            if(next == nullptr) break;
            ListNode* node = next->next;
            if(pre != nullptr) {
                pre->next = next;
            }
            pre = cur;
            cur->next = node;
            next->next = cur;
            cur = node;
        }
        return ans;

    }
};

[JasonQiu]

• Create dummy head prev and save the new head
• Swap when there are at least two nodes remaining

  class Solution:
  def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
      prev = ListNode(0, head)
      if head and head.next:
          head = head.next
      while prev.next and prev.next.next:
          left = prev.next
          right = left.next
          prev.next = right
          left.next = right.next
          right.next = left
          prev = left
      return head

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

[yingchehu]

Code

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

        ret = self.swapPairs(head.next.next)
        tmp = head.next
        head.next = ret
        tmp.next = head

        return tmp

複雜度

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

[linlizzz]

思路

1）若只有一个元素或没有元素时直接return

2）定义两个指针，交换其next，并连接前一个元素，依次向后移动，直至没有元素或只剩一个

代码

​​​​​class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head and head.next:
            res = head.next
            p = head
            q = head.next
            e = None
            while True:
                p.next = q.next
                q.next = p
                if e:
                    e.next = q
                if p.next == None or p.next.next == None:
                    break
                else:
                    e = p
                    p = p.next
                    q = p.next
        else:
            res = head
        return res

复杂度分析

T(n)=O(n)

S(n)=O(1)

[KrabbeJing]

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

        while temp.next and temp.next.next:
            p1 = temp.next
            p2 = temp.next.next
            temp.next = p2
            p1.next = p2.next
            p2.next = p1
            temp = p1

        return fake_head.next

[FireHaoSky]

思路：

""" 通过一个中间节点分别指向之后的两个节点，然后将这个中间节点推进至第二个节点的位置，重复上述过程，知道没有节点或只有一个节点的时候。 """

解题：python

class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: middle = ListNode[0] middle.next = head temp = middle while temp.next and temp.next.next: node1 = temp.next node2 = temp.next.next temp.next = node2 node1.next = node2.next node2.next = node1 temp = node1 return middle.next

复杂度分析：

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

[yuzmt]

思路

使用递归，注意留口子结束递归

代码

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

    const curHead = head.next;
    head.next = swapPairs(curHead.next);
    curHead.next = head;
    return curHead;
};

复杂度

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

[zhangyong-hub]

思路

递归，注意终止条件

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next)
            return head;
        ListNode *newhead = head->next;
        head->next = swapPairs(newhead->next);
        newhead->next = head;
        return newhead;

    }
};

[texamc2]

func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := head.Next
    head.Next = swapPairs(newHead.Next)
    newHead.Next = head
    return newHead
}

[mengsixing]

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode temp = pre;
        while(temp.next != null && temp.next.next != null) {
            ListNode start = temp.next;
            ListNode end = temp.next.next;
            temp.next = end;
            start.next = end.next;
            end.next = start;
            temp = start;
        }
        return pre.next;
    }
}

[dorapocket]

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==nullptr) return head;
        ListNode top(-1,head);
        ListNode* p0=&top,*p1=head,*p2=head->next,*p3;
        p2=p1==nullptr?nullptr:p1->next;
        while(p1!=nullptr&&p2!=nullptr){
            p3=p2->next;
            p0->next=p2;
            p0=p2->next=p1;
            p1=p1->next=p3;
            p2=p3==nullptr?p3:p3->next;
            p3=p2==nullptr?p3:p2->next;
        }
        return top.next;
    }
};

[jyjsunny]

思路

• 方法一：设置pre和node，每两个点为一组表示关系、进行交换（看重链表性质以及构造逻辑）
• 方法二：两点为一组，递归求解（利用递归特性）

代码

//方法一：利用list逻辑
    public static ListNode SwapList(ListNode node){
        if(node==null||node.next==null)  return node;
        ListNode newhead = node.next;
        ListNode pre = new ListNode();
        pre.next = node;

        while(node!=null&&node.next!=null){
            pre.next = node.next;
            node.next = node.next.next;
            pre.next.next = node;
            pre = node;
            node = pre.next;
        }

        return newhead;
    }
//方法二：利用递归
    public static ListNode SwapList(ListNode node){
        //方法二：递归
        //递归：1）终止条件，2）返回值，3）单步过程
        //终止条件
        if(node==null||node.next==null)
        {
            return node;
        }
        ListNode next = node.next;
        //单步过程
        node.next= SwapList(next.next);
        next.next=node;
        //返回值
        return next;
    }

[kangliqi1]

public ListNode swapPairs(ListNode head) { ListNode temp = new ListNode(0,head); ListNode ans = temp; while(head!=null&&head.next!=null){ temp.next = temp.next.next; head.next = head.next.next; temp.next.next = head; head = head.next; temp = temp.next.next; } return ans.next; }

[zhangjiahuan17]

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