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.
思路
cur和cur->next 分别表示需要交换的两个节点，pre表示交换的第一个节点的前一个节点。经过下述操作，就能达到交换的目的。顺序很重要。
pre->next=cur->next;
cur->next=cur->next->next;
pre->next->next=cur;
然后移动操作。
pre=cur
cur=cur->next
解题
c++版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(!head)
return NULL;
ListNode dummy(-1);
dummy.next=head;
ListNode *pre,*cur;
pre=&dummy;
cur=head;
while(cur and cur->next){
pre->next=cur->next;
cur->next=cur->next->next;
pre->next->next=cur;
pre=cur;
cur=cur->next;
}
return dummy.next;
}
};
|
Python版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution:
def swapPairs(self, head):
dummy=ListNode(-1)
dummy.next=head
pre=dummy
cur=pre.next
while cur and cur.next:
pre.next=cur.next
cur.next=pre.next.next
pre.next.next=cur
pre=cur
cur=cur.next
return dummy.next
|
