【Day 8 】2024-04-15 - 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

[Martina001]

思路：这是一个递归解法的优秀范例： private ListNode swapPair2(ListNode head){ if(head == null || head.next == null){ return head; } ListNode temp = head; head = head.next; head.next = temp; head.next.next = swapPair2(head.next.next); return head; }

时间复杂度On 空间复杂度为On（递归用到了栈）

[zhiyuanpeng]

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        num = 0
        p = head
        while p:
            num += 1
            p = p.next
        swap_num = int(num/2)
        cur_p = head
        pre = ListNode(next=head)
        for i in range(swap_num):
            next_p = cur_p.next
            cur_p.next = next_p.next
            next_p.next = cur_p
            pre.next = next_p
            pre = cur_p
            if i == 0:
                new_head = next_p
            cur_p = cur_p.next
        return new_hea

time O(N) space O(1)

[coderXiaowq]

Java 时间复杂度O(n) 使用虚拟头结点

public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode dummy = new ListNode(666, head);
        ListNode cur = dummy;
        // 交换1号和2号 cur.next和cur.next.next
        while (cur.next != null && cur.next.next != null) {
            ListNode first = cur.next;// 记录1号
            ListNode seconde = cur.next.next;// 记录2号 用以访问下一个1号
            first.next = seconde.next;// 1号指向下一个1号
            seconde.next = first;// 2号指向1号
            cur.next = seconde;// cur指向2号并且dummy第一次指向2号
            // cur.next再次指向下一组1号
            cur = first;
        }
        return dummy.next;
    }

[lxy1108]

思路 采用迭代的方式，每次迭代交换当前指针后面的两个节点，直到当前指针后面的节点不足两个循环停止

Python3 代码

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

复杂度分析 时间复杂度O(n)，即为循环执行次数，n为节点个数 空间复杂度O(1)

[wwz223]

代码

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

    let tmp = head.next;
    head.next = swapPairs(tmp.next);
    tmp.next = head;
    return tmp;
};

复杂度分析

• 时间复杂度 O（N）
• 空间复杂度 每两个节点的交换需要借助一个节点， O（1/2N）

[hillsonziqiu]

思路

递归交换链表相邻两个值即可

代码

var swapPairs = function(head) {
    if (!head?.next) return head;

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

复杂度分析

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

[eclairs46]

思路

定义临时变量 next 保存下一个节点的下一个节点，交换 head 和 head.next 两个节点的位置

代码

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

复杂度分析

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

[xil324]

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    if(head === null || head.next === null) return head;
    let first = head, second = head.next, rest = head.next.next;
    second.next = first;
    first.next = swapPairs(rest);
    return second; 
};

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

[GReyQT]

题解思路：

（1）分解子问题：每一次都是两个节点交换的问题 （2）子问题推导递推公式： newHead = head->next; head->next = newHead->next; newHead->next = head; （2）判断递归终止条件：链表剩余为空或者仅一个节点 代码：

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

复杂度分析：

• 时间复杂度：取决于链表的长度n，因此时间的复杂度为O(n)
• 空间复杂度：取决于链表的长度n，每一层递归调用都会使用一定的堆栈空间，因此空间复杂度为 O(1)

[franklinsworld666]

思路

递归，先解决空链表、一个节点或两个节点的问题。然后递归结果剩下的。

代码

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

复杂度分析

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

[YANGLimbo]

递归，每次处理完一对节点，把后面的作为整体进行处理

/**
 * 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 == nullptr){
            return nullptr;
        }
        if(head->next == nullptr){
        //单数,最后一个元素
            return head;
        }
        ListNode* first = head;
        ListNode* second = head->next;

        first->next = swapPairs(second->next);
        second->next = first;
        return second;
    }
};

[CathyShang]

思路：

• 迭代

• 间1隔选取相邻2个节点进行交换 （循环程序写的不对，死循环） 代码：

  class Solution {
  public:
  ListNode* swapPairs(ListNode* head) {
      // 不通过，循环超时
      // 小于1
      if(head==nullptr||head->next==nullptr)return head;
      ListNode* cur = head;
      ListNode* temp = head->next;
      ListNode* temp2;
      ListNode* preHead=new ListNode(-1);
      ListNode* res=preHead;
      while(cur!=nullptr && temp!=nullptr){
          std::cout << cur->val << endl;
          // if(temp->next!=nullptr) temp2=temp->next;
          // else{ temp2=nullptr; }
          // cur->next = nullptr;
          // temp->next = cur;
          // cur->next = temp2;
          res->next = temp;
          cur->next = temp->next;
          temp->next = cur;
          // temp->next = cur;
          //
          cur=cur->next->next;
          if(temp->next==nullptr) break;
          else{temp->next->next;}
      }
      return preHead->next;
  
  }
  };

复杂度：

• 时间 $O(N)$
• 空间 $O(N)$

[smallppgirl]

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

[Alexzhang-Mini]

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

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

        return dummy.next

[atom-set]

思路

分支 1: 边界条件判断，直接返回 head

• 链表为空
• 链表长度为 1

分支 2: 两两交互

• step1: 定义两个指针，p1 和 p2, p2 是 p1 的后继
• step2: 迭代逻辑，p1 和 p2 都不为看空，先进行交互，然后分别前进 2 位
• step3: 退出条件：p1 和 p2 至少有 1 个为空

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var swapPairs = function (head) {
  // 边界条件判断
  if (!head || (head && !head.next)) {
    return head;
  }

  var p1 = new ListNode(0);
  var p2 = new ListNode(0);
  var p3 = new ListNode(0);
  var p4 = new ListNode(0);
  p1 = head;
  p2 = p1.next;
  p3.next = head;

  // p3 -> 1 -> 2
  // step1: p3 -> 1 <- 2
  // step2: 1 <- 2 <- p3

  while (p2) {
    var nextP1 = p2.next;
    var nextP2 = p2.next ? p2.next.next : null;
    p2.next = p1;
    p3.next = p2;
    p1.next = null;
    if (!p4.next) {
      p4.next = p3.next;
    }

    p3 = p3.next.next;

    p1 = nextP1;
    p2 = nextP2;
  }

  if (p1) {
    p3.next = p1;
  }
  return p4.next;
};

复杂度分析 对链表进行一次遍历即可

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

[rao-qianlin]

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 空链表、只有一个元素的链表不用交换
        if(head == null || head.next == null){
            return head;
        }

        ListNode temph = new ListNode(0);
        temph.next = head;
        ListNode slow = temph;
        ListNode fast = temph.next.next;

        while(fast.next != null && fast.next.next != null){
            ListNode temp = fast.next;
            fast.next = slow.next;
            slow.next = fast;
            fast = fast.next;
            fast.next = temp;

            slow = slow.next.next;
            fast = fast.next.next;
        }
        if(fast.next == null){
            fast.next = slow.next;
            slow.next = fast;
            fast = fast.next;
            fast.next = null;
        }
        else if(fast.next.next == null){
            ListNode temp = fast.next;
            fast.next = slow.next;
            slow.next = fast;
            fast = fast.next;
            fast.next = temp;
        }
        return temph.next;
    }
}

[pandapls]

var swapPairs = function(head) {
    let dummyNode = new ListNode(-1);
    dummyNode.next = head;

    let node = dummyNode;

    while(node && node.next && node.next.next) {
        let prev = node;
        let curNode = prev.next;
        let tmp = curNode.next;
        curNode.next = tmp.next;
        tmp.next = prev.next;
        prev.next = tmp;

        node = curNode
    }

    return dummyNode.next
};

复杂度分析

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