【每日一题Day287】LC24 两两交换链表中的节点 | 模拟 递归

两两交换链表中的节点【LC24】

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

周赛暂停一周啦

• 思路：模拟

  记录前驱节点，如果接下来还有两个不为空的节点时，将其交换。

  • 2022/4/15
  • 2023/8/6

  /*** 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 dummyNode = new ListNode(-1,head);ListNode pre = dummyNode;ListNode cur = pre.next;while(pre != null && cur !=null && cur.next != null){ListNode tmp = cur.next.next;pre.next = cur.next;cur.next.next = cur;cur.next = tmp;pre = cur;cur = cur.next;}return dummyNode.next; }
  }
  

• 实现：直接从前驱节点出发

  2022/09/21
  class Solution {public ListNode swapPairs(ListNode head) {ListNode dummyHead = new ListNode(0,head);ListNode node = dummyHead;while (node.next != null && node.next.next != null){ListNode nn = node.next.next;node.next.next = nn.next;nn.next = node.next;node.next = nn;node = node.next.next;}return dummyHead.next;}
  }
  

  • 复杂度
    • 时间复杂度：$\mathcal{O}(n)$
    • 空间复杂度：$\mathcal{O}(1)$

• 递归

  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;}
  }作者：LeetCode-Solution
  链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/liang-liang-jiao-huan-lian-biao-zhong-de-jie-di-91/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  

  • 复杂度
    • 时间复杂度：$\mathcal{O}(n)$
    • 空间复杂度：$\mathcal{O}(n)$