兩兩交換鏈表中的節(jié)點【LC24】

給你一個鏈表，兩兩交換其中相鄰的節(jié)點，并返回交換后鏈表的頭節(jié)點。你必須在不修改節(jié)點內部的值的情況下完成本題（即，只能進行節(jié)點交換）。

周賽暫停一周啦

• 思路：模擬

  記錄前驅節(jié)點，如果接下來還有兩個不為空的節(jié)點時，將其交換。

  • 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; }
  }
  

• 實現(xiàn)：直接從前驅節(jié)點出發(fā)

  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）
  著作權歸作者所有。商業(yè)轉載請聯(lián)系作者獲得授權，非商業(yè)轉載請注明出處。
  

  • 復雜度
    • 時間復雜度：$\mathcal{O}(n)$
    • 空間復雜度：$\mathcal{O}(n)$