24. 兩兩交換鏈表中的節(jié)點(diǎn)
給定一個(gè)鏈表松蒜，兩兩交換其中相鄰的節(jié)點(diǎn)窄赋，并返回交換后的鏈表僚纷。
- 你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值从橘，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換念赶。
示例1:
給定 1->2->3->4, 你應(yīng)該返回 2->1->4->3.
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/swap-nodes-in-pairs/
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)恰力，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處叉谜。
-
1.迭代法
思路：(使用雙指針進(jìn)行交換)
- 我們維護(hù)一個(gè)頭節(jié)點(diǎn) prev, 由頭節(jié)點(diǎn)創(chuàng)建兩個(gè)指針 slow = prev.next, fast = prev.next.next
- 交換 slow 和 fast 節(jié)點(diǎn)的位置
- 交換完成之后將 slow 節(jié)點(diǎn)指向 prev, 用于交換下一組節(jié)點(diǎn)
image.png
public static class ListNode {
private int val;
private ListNode next;
public ListNode(int val) {
this.val = val;
}
//用于測(cè)試用例
public ListNode(int[] arr) {
if (arr == null || arr.length == 0) throw new NullPointerException("array is Empty");
this.val = arr[0];
ListNode cur = this;
for (int i = 1; i < arr.length; i++) {
cur.next = new ListNode(arr[i]);
cur = cur.next;
}
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
ListNode cur = this;
while (cur != null) {
res.append(cur.val + "->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}
public static ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode prev = dummyHead;
while (prev.next != null && prev.next.next != null) {
ListNode slow = prev.next;
ListNode fast = prev.next.next;
slow.next = fast.next;
prev.next = fast;
fast.next = slow;
prev = slow;
}
return dummyHead.next;
}
復(fù)雜度分析：
時(shí)間復(fù)雜度：O(n), n 為鏈表的長(zhǎng)度，我們需要遍歷整個(gè)鏈表
空間復(fù)雜度：O(1), 只需要常數(shù)級(jí)別的空間復(fù)雜度
-
2. 遞歸法
思路：從宏觀上考慮
- 先考慮遞歸結(jié)束條件：當(dāng)鏈表為空或者只有一個(gè)元素則不需要進(jìn)行交換
- 我們先創(chuàng)建一個(gè)節(jié)點(diǎn)next指向head.next,假設(shè)next后面的鏈表是已經(jīng)排好序的
- 那么踩萎，我們只需將鏈表前兩位元素調(diào)換位置即可
public static ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode next = head.next;
head.next = swapPairs2(next.next);
next.next = head;
return next;
}
復(fù)雜度分析：
時(shí)間復(fù)雜度：O(n), n 為鏈表長(zhǎng)度
空間復(fù)雜度：O(n)停局，由于使用了遞歸，深度可能達(dá)到n層
-
測(cè)試用例
public static void main(String[] args) {
int[] arr = new int[] {1, 2, 3, 4};
ListNode listNode = new ListNode(arr);
System.out.println(listNode);
System.out.println("兩兩交換鏈表中的節(jié)點(diǎn)" + swapPairs2(listNode));
}
-
結(jié)果
1->2->3->4->NULL
兩兩交換鏈表中的節(jié)點(diǎn)2->1->4->3->NULL
-
源碼
-
我會(huì)每天更新新的算法，并盡可能嘗試不同解法董栽，如果發(fā)現(xiàn)問(wèn)題請(qǐng)指正
- Github
