【基础篇 - Day 8】 2023-02-20 - 24. 两两交换链表中的节点 （02. 链表 ）

[threedayAAAAA]

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

 

示例 1：

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

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

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

提示：

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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/swap-nodes-in-pairs 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

思路

• 编写一个函数用于判断是否需要两两交换节点，比如奇数节点或者当前节点不存在时则不用交互
• 编写一个函数用于交互临近的两个节点，思路如下
• 申请一个虚拟的头节点，获取下一个节点（新尾）、下下个节点（新头）、原先尾节点的后续链表
• 虚拟头节点next ===> 新头
• 新头next ===> 新尾
• 新尾 next ===> 后续链表
• 使用循环每次重复上述操作即可
• 上述思路主要在于申请一个虚拟的头节点，这样编码时就可不用考虑当前节点是否是头节点这种边界，逻辑更加顺畅

代码

function swapPairs(head: ListNode | null): ListNode | null {
    const result = new ListNode(0, head)
    let currentPreNode = result
    while(hasTwoNode(currentPreNode)){
        swapTwoNode(currentPreNode)
        currentPreNode = currentPreNode.next.next
    }
    return result.next
};

function hasTwoNode(preNode: ListNode | null): boolean{
    return Boolean(preNode?.next?.next)
}

function swapTwoNode(preNode: ListNode | null){
    const newHeadNode = preNode.next.next
    const newEndNode = preNode.next
    const originTailLink = preNode.next.next.next
    preNode.next = newHeadNode
    newHeadNode.next = newEndNode
    newEndNode.next = originTailLink
}

时空复杂度

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

[yunliuyan]

思路

• 若head为空或者链表只有一个节点，则返回当前节点
• 创建一个虚拟节点vNode，next指向head
• 当vNode.next(node1)和vNode.next.next(node2)都存在时，则只需要迭代这段逻辑 node1.next = node2.next,node2.next = node1,vNode.next = node2, vNode = node1这段逻辑即可

代码

function swapPairs(head: ListNode | null): ListNode | null {
  if (!head || !head.next) {
    return head;
  }
  let vNode = new ListNode();
  vNode.next = head;
  let tempNode = vNode;
  while(tempNode?.next?.next) {
    const node1 = tempNode.next;
    const node2 = tempNode.next.next;
    node1.next = node2.next;
    tempNode.next = node2;
    node2.next = node1;
    tempNode = node1;
  }
  return vNode.next;
};

复杂度分析

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

[MiumMi]

方案一

思路

1. 遍历整条链表，当size为偶数倍的时候去交换两个节点

2. 因为这里是俩俩交换，所以其实不知道上一个节点的指向，这里利用映射表来保存需要交换的值的上一个节点，如果在映射表上存在这个需要交换的值，则同步更新上一个节点的next

   代码

   
   /**
   * Definition for singly-linked list.
   * class ListNode {
   *     val: number
   *     next: ListNode | null
   *     constructor(val?: number, next?: ListNode | null) {
   *         this.val = (val===undefined ? 0 : val)
   *         this.next = (next===undefined ? null : next)
   *     }
   * }
   */

function swapPairs(head: ListNode | null): ListNode | null { if (!head || !head.next) { return head; } let size = 0; let currentNode = head; let startNode; let dataMap = new Map(); while(currentNode?.next) { if (size % 2 === 0) { const temp = currentNode.next; const newHead= temp.next; if (dataMap.has(currentNode)) { dataMap.get(currentNode).next = temp; } temp.next = currentNode; if (size === 0) { startNode = temp; } currentNode.next = newHead; // 相当于跳过了一个节点 size++; dataMap.set(newHead, currentNode); } currentNode = currentNode.next; size++; } return startNode; };

---
### 分析
1. 时间复杂度分析：O(n)
2. 空间复杂度分析: O(n)

<h1>方案二</h1>
### 思路
1. 分析方案1，如果当前有A、B、C、D、E等节点，实际上当前node的next是不需要遍历的，如： B、D，他们会直接被A、C交换，所以循环的时候直接判断node.next.next即可
2. 这个思路交换的时候同时计算3个节点： 当前节点（即思路1中缓存起来需要更新next的节点），需要交换当前节点后的2个节点；并且更新当前指向结点的next。交换完成后的尾结点作为新的指向结点开始遍历计算下次需要交换的2个节点
---
### 代码

function swapPairs(head: ListNode | null): ListNode | null { if (!head || !head.next) { return head; } const headNode = new ListNode(0, head); let currentNode = headNode; while(currentNode?.next?.next) { const newHead = currentNode.next.next; const newEnd = currentNode.next; currentNode.next = newHead; newEnd.next = newHead.next; newHead.next = newEnd; currentNode = newEnd; } return headNode.next; };

---
### 分析
1. 时间复杂度分析：O(n)
2. 空间复杂度分析：O(1)

[MiumMi]

方案二

思路

1. 分析方案1，如果当前有A、B、C、D、E等节点，实际上当前node的next是不需要遍历的，如： B、D，他们会直接被A、C交换，所以循环的时候直接判断node.next.next即可
2. 方案1中，因为是俩俩交换，导致需要一个新的内存空间来保存需要更新next的节点。那此时我们交换的时候同时计算3个节点： 当前节点（即思路1中缓存起来需要更新next的节点），需要交换当前节点后的2个节点；并且更新当前指向结点的next。交换完成后的尾结点作为新的指向结点开始遍历计算下次需要交换的2个节点

---

代码

function swapPairs(head: ListNode | null): ListNode | null {
    if (!head || !head.next) {
        return head;
    }
    const headNode = new ListNode(0, head);
    let currentNode = headNode;
    while(currentNode?.next?.next) {
      const newHead = currentNode.next.next;
      const newEnd = currentNode.next;
      currentNode.next = newHead;
      newEnd.next = newHead.next;
      newHead.next = newEnd;
      currentNode = newEnd;
    }
    return headNode.next;
};

---

分析

1. 时间复杂度分析：O(n)
2. 空间复杂度分析：O(1)