目錄
- 1、題目
- 2、思路
- 3、c++代碼
- 4、java代碼
1、題目
給定一個鏈表，兩兩交換其中相鄰的節點，并回傳交換后的鏈表，
你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換，
示例 1：
輸入：head = [1,2,3,4]
輸出：[2,1,4,3]
示例 2：
輸入：head = []
輸出：[]
示例 3：
輸入：head = [1]
輸出：[1]
提示：
- 鏈表中節點的數目在范圍
[0, 100]內 0 <= Node.val <= 100
2、思路
(模擬) O ( n ) O(n) O(n)
題目給定一個鏈表，要求我們兩兩交換其中相鄰的節點，并回傳交換后的鏈表，由于可能會對頭節點進行改變，因此需要建立一個虛擬頭結點dummy，指向原來的頭節點，
根據題意進行模擬迭代，兩兩交換相鄰兩個結點，如下圖所示：
具體程序詳解：
-
1、首先定義
p = dummy，a = p->next，b = a->next， -
2、遍歷整個鏈表，第一步先將
p的next指標指向b，即p->next = b， -
3、然后將
a的next指向b->next，即a->next = b->next， -
4、最后將
b的next指向a，即b->next = a，經過上述操作以后，我們就成功交換了
a，b節點，然后讓p指向a節點，重復上述操作即可，
- 5、最后回傳虛擬頭節點的下一個節點
時間復雜度分析： O ( n ) O(n) O(n)，其中 n n n是鏈表的節點數量，
3、c++代碼
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(-1); //虛擬頭節點
dummy->next = head;
for(auto p = dummy; p->next && p->next->next; )
{
auto a = p->next, b = a->next;
p->next = b;
a->next = b->next;
b->next = a;
p = a;
}
return dummy->next;
}
};
4、java代碼
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
for(ListNode p = dummy; p.next != null && p.next.next != null;)
{
ListNode a = p.next; //虛擬頭節點
ListNode b = a.next;
p.next = b;
a.next = b.next;
b.next = a;
p = a;
}
return dummy.next;
}
}
原題鏈接： 24. 兩兩交換鏈表中的節點
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/294462.html
標籤：java
上一篇：# Day11-Java基礎