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 要改变位置。还要有一个 pre 指针。
/**
* 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 *pre = NULL, *p = head;
while(p && p->next) {
ListNode *q = p->next;
p->next = q->next;
q->next = p;
if(pre == NULL) head = q;
else pre->next = q;
pre = p;
p = p->next;
}
return head;
}
};
Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.
注意： 前两个互换的时候，head 要改变位置。还要有一个 pre 指针。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
int getLength(ListNode *head) {
int len = 0;
while(head) {
++len;
head = head->next;
}
return len;
}
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
if(head == NULL) return NULL;
k = k % getLength(head);
if(k == 0) return head;
ListNode *first, *second, *preFirst;
first = second = head;
for(int i = 1; i < k && second->next; ++i) // k-1 step
second = second->next;
//if(second->next == NULL) return head;
while(second->next) {
preFirst = first;
first = first->next;
second = second->next;
}
second->next = head;
preFirst->next = NULL;
return first;
}
};
Remove Nth Node From End of List
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
Note: Given n will always be valid. Try to do this in one pass.
思路： 双指针。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n) {
ListNode *pre = NULL, *p1, *p2;
p1 = p2 = head;
for(int i = 1; i < n; ++i) p2 = p2->next;
while(p2->next) {
pre = p1;
p1 = p1->next;
p2 = p2->next;
}
if(pre) pre->next = pre->next->next;
return pre ? head : head->next;
}
};