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.
--------
Solution #1
pre has the address of "next" of the previous node
pre can be replace by a ListNode* type.
/**
* 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) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
ListNode *saved;
ListNode **pre;
if (head != NULL && head->next != NULL) {
saved = head->next;
pre = &(head->next);
}else {
return head;
}
while (head != NULL && head->next != NULL) {
*pre = head->next;
ListNode *temp = head->next->next;
head->next->next = head;
head->next = temp;
pre = &(head->next);
head = temp;
}
return saved;
}
};
Update on Sep-03-2014
Solution #2, with dummy node
/**
* 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) {
ListNode *dummy;
dummy->next = head;
ListNode *itr = dummy;
while (head != NULL && head->next != NULL) {
itr->next = head->next;
ListNode *temp = head->next->next;
head->next = temp;
itr->next->next = head;
itr = head;
head = temp;
}
return dummy->next;
}
};
Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2[1,3,5,6], 2 → 1[1,3,5,6], 7 → 4[1,3,5,6], 0 → 0
-----------------------------------
For #2, #3, if match is not found, compare target with A[start] to determine the final position
Solution #1 O(n)
class Solution {
public:
int searchInsert(int A[], int n, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
for(int i=0;i<n;i++) {
if (A[i] >= target) {
return i;
}
}
return n;
}
};
Solution #2 O(log n), recursiveclass Solution {
public:
int rec (int A[], int start, int end, int target) {
if (start >= end) {
if (A[start] >= target) {
return start;
}
return start+1;
}
int mid = (start + end) / 2;
if (A[mid] == target) {
return mid;
}
if (A[mid] < target) {
return rec(A,mid+1,end,target);
}else {
return rec(A,start,mid-1,target);
}
}
int searchInsert(int A[], int n, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return rec(A,0,n-1,target);
}
};
Solution #3 O(log n)class Solution {
public:
int searchInsert(int A[], int n, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int start = 0, end = n-1;
while (start < end) {
int mid = (start + end) / 2;
if (A[mid] == target) {
return mid;
}
if (A[mid] < target) {
start = mid + 1;
}else {
end = mid - 1;
}
}
if (A[start] >= target) {
return start;
}else {
return start+1;
}
}
};
another version
class Solution {
public:
int searchInsert(int A[], int n, int target) {
int mid = n / 2;
int left = 0, right = n - 1;
while (left <= right) {
mid = (left + right) / 2;
if (A[mid] == target) {
return mid;
}
if (A[mid] > target) {
right = mid - 1;
}else {
left = mid + 1;
}
}
return right + 1;
}
};
