Repository navigation
Expand file tree
/
Copy pathswapNodesInPairs.cpp
More file actions
74 lines (70 loc) · 2.09 KB
/
Copy pathswapNodesInPairs.cpp
File metadata and controls
74 lines (70 loc) · 2.09 KB
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// Source : https://oj.leetcode.com/problems/swap-nodes-in-pairs/
// Author : Hao Chen
// Date : 2014-06-22
/**********************************************************************************
*
* 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.
*
*
**********************************************************************************/
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
Solution(){
srand(time(NULL));
}
/*
* Here we have two ways to solve this problem:
* 1) keep the list's nodes no change. only swap the data in the list node.
* 2) swap the list node physically.
*/
ListNode *swapPairs(ListNode *head) {
if(random()%2){
return swapPairs1(head);
}
return swapPairs2(head);
}
/*just swap the node's value instead of node*/
ListNode *swapPairs1(ListNode *head) {
for (ListNode *p = head; p && p->next; p = p->next->next) {
int n = p->val;
p->val = p->next->val;
p->next->val = n;
}
return head;
}
/*swap the list nodes physically*/
ListNode *swapPairs2(ListNode *head) {
ListNode *h = NULL;
//using `*p` to traverse the linked list
for (ListNode *p = head; p && p->next; p = p->next) {
//`n` is `p`'s next node, and swap `p` and `n` physcially
ListNode *n = p->next;
p->next = n->next;
n->next = p;
//using `h` as `p`'s previous node
if (h){
h->next = n;
}
h=p;
//determin the really 'head' pointer
if (head == p){
head = n;
}
}
return head;
}
};