LeetCode --- 24. Swap Nodes in Pairs
タイトルリンク:Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
この問題の要求はチェーンテーブルの隣接するノードを交換することである.要件:一定のスペースを使用すると、チェーンテーブルの数値の変更は許可されず、チェーンテーブルノード自体のみを変更できます.
この問題はチェーンテーブル処理を考察しているが,同様にチェーンテーブルの前に頭を加え,チェーンテーブルのすべてのノードを統一的に処理するのに便利である.
時間複雑度:O(n)
空間複雑度:O(1)
転載は出典を説明してください:LeetCode---24.Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
この問題の要求はチェーンテーブルの隣接するノードを交換することである.要件:一定のスペースを使用すると、チェーンテーブルの数値の変更は許可されず、チェーンテーブルノード自体のみを変更できます.
この問題はチェーンテーブル処理を考察しているが,同様にチェーンテーブルの前に頭を加え,チェーンテーブルのすべてのノードを統一的に処理するのに便利である.
:
head -> 1 -> 2 -> 3 -> 4 -> NULL。
:
h -> 0 -> 1 -> 2 -> 3 -> 4 -> NULL。
p ,temp , :
h -> 0 -> 1 -> 2 -> 3 -> 4 -> NULL
^ ^
| |
p temp
, 1 2 , , p->next 2:
|-------->|
h -> 0 1 -> 2 -> 3 -> 4 -> NULL
^ ^
| |
p temp
temp->next 3:
|-------->|
h -> 0 1 2 -> 3 -> 4 -> NULL
^ |-------->|
| ^
p |
temp
2 next 1:
|-------->|
h -> 0 1 <- 2 3 -> 4 -> NULL
^ |-------->|
| ^
p |
temp
:
h -> 0 -> 2 -> 1 -> 3 -> 4 -> NULL
^ ^
| |
p temp
p ( temp ) :
h -> 0 -> 2 -> 1 -> 3 -> 4 -> NULL
^
|
p
3 4, , 。。。
時間複雑度:O(n)
空間複雑度:O(1)
1 class Solution
2 {
3 public:
4 ListNode *swapPairs(ListNode *head)
5 {
6 ListNode *h = new ListNode(0), *p = h;
7 h -> next = head;
8
9 while(p -> next != NULL && p -> next -> next != NULL)
10 {
11 ListNode *temp = p -> next;
12 p -> next = temp -> next;
13 temp -> next = p -> next -> next;
14 p -> next -> next = temp;
15 p = temp;
16 }
17
18 return h -> next;
19 }
20 };
転載は出典を説明してください:LeetCode---24.Swap Nodes in Pairs