206. Reverse Linked List
描述:
Reverse a singly linked list.
Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?
分析；
经典的一道链表习题，要求逆置链表，方法有迭代和递归两种
1.迭代:迭代的方法就是遍历整个链表，将指向下一结点的指针改变方向，要注意的是因为单链表无法直接找到某个结点的前驱，所以我们需要三个指针，用来记录当前结点，当前节点的后继和其后继的后继，代码如下:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head||!head->next)
return head;
struct ListNode *cur=head,*pnext=cur->next,*prev=NULL;
cur->next=NULL;
while(pnext){
prev=pnext->next;
pnext->next=cur;
cur=pnext;
pnext=prev;
}
head=cur;
return head;
}
};
2.递归:
递归的思路比较巧妙，它假设链表此时除了第k个结点之前的结点，其余结点已经全部置逆，即如下的情况:
n1 → … → nk-1 → nk → nk+1 ← … ← nm
那么此时我们需要的操作就是让第k个结点也呈逆置的状态:
即:
head->next-next=head;
head->next=NULL;
递归代码如下:
/*Recursion*/
struct ListNode* reverseList(struct ListNode* head) {
if(!head)
return head;
struct ListNode * p=reverselist(head->next);
head->next-next=head;
head->next=NULL;
return p;
}
143. Reorder List
描述:
Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes’ values.
For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.
分析:
要求对链表进行重新排序，排序的规则见题干。
由于要求了in-place，所以时间复杂度只能是O(1)，那么我们可以先对后半段链表进行逆序，之后与前半段链表进行合并即可，代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
struct ListNode * reverseList(struct ListNode *head){
if(!head||!head->next)
return head;
struct ListNode *cur=head,*pnext=cur->next,*prev=NULL;
cur->next=NULL;
while(pnext){
prev=pnext->next;
pnext->next=cur;
cur=pnext;
pnext=prev;
}
head=cur;
return head;
}
public:
void reorderList(ListNode* head) {
if(!head||!head->next)
return;
struct ListNode *fast=head,*slow=head,*right=NULL,*pmove=head,*qmove=NULL;
while(fast&&fast->next){
slow=slow->next;
fast=fast->next->next;
}
right=slow->next;
slow->next=NULL;/*从中间截断*/
right=reverseList(right);
qmove=right;
pmove=head;
int index=0;
/*对于奇数个和偶数个要分两种情况*/
while(pmove&&qmove){
if(index%2==0){
struct ListNode * next=pmove->next;
pmove->next=qmove;
pmove=next;
}
else{
struct ListNode * next=qmove->next;
qmove->next=pmove;
qmove=next;
}
index++;
}
}
};
61. 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.
分析:
这道题在发现规律之后也很简单，思路与上面的题有些类似，但我们根据链表的一些性质可以降低空间复杂度到常数级。
我们首先遍历整个链表，同时计算长度len并将最后一个结点的next指针指向head，形成一个循环链表，考虑到k值可能大于len，所以我们令k%=len,之后指针再向前移动len-k步，从这里断开整个循环链表即可，代码如下:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* rotateRight(struct ListNode* head, int k) {
if(!head||!head->next||k<=0)
return head;
struct ListNode *pmove=head;
int len=1;
while(pmove->next){
pmove=pmove->next;
len++;
}
pmove->next=head;
k=len-k%len;
while(k){
pmove=pmove->next;
k--;
}
head=pmove->next;
pmove->next=NULL;
return head;
}
328. Odd Even Linked List
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.
Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on …
这道题要求我们调整链表次序，使其满足位序为奇数的结点相连之后与位序为偶数的结点相连。
我们可以使用三个指针，odd，even和even_head，其中even_head用于记录位序为偶数结点组成的的链表的头部，便于之后与奇数结点组成的链表相连。
我们最开始可以让odd指向第一个结点，even指向第二个，因为even之后又是odd，所以odd之后应该接even的后继结点，并且将odd后移，如此反复，最后将odd与even_head相连接。
代码如下:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if(!head||!head->next)
return head;
struct ListNode *odd=head,*even_head=head->next,*even=even_head;
while(even&&even->next){
odd->next=even->next;
odd=odd->next;
even->next=odd->next;
even=even->next;
}
odd->next=even_head;
return head;
}
};
86. Partition List
描述:
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2and x = 3,
return 1->2->2->4->3->5.
分析:
这道题考察快速排序的思想，但没有要求sort只要求了partition（还要求partition前后元素相对位置不能改变），所以用一个指针遍历原链表，分两种情况：
1. 结点值小于val，放入链表1 2. 其余情况放入链表2
之后连接两个链表即可。
可以在纸上模拟这两个过程，会发现最终是不会改变相对位置的。
代码如下:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
struct ListNode left(0),right(0);
struct ListNode *pLeft=&left,*pRight=&right;
if(!head)
return head;
while(head){
if(head->val<x){
pLeft->next=head;
pLeft=pLeft->next;
}
else{
pRight->next=head;
pRight=pRight->next;
}
head=head->next;
}
pRight->next=NULL;
pLeft->next=right.next;
return left.next;
}
};
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.
分析:
这道题让我们成对交换链表中的结点，只能改变指针指向不能改变节点的值。
那么我们需要维护三个指针，一个用来记录一对结点的后继结点的指针nextstart，另外两个记录一对结点的两个指针ptr1,ptr2，之后交换结点并将交换后的一对结点重新接回链表即可。
需要讨论的地方在于，最终状态下，当链表为奇数个结点时,ptr2->next==NULL,为偶数个结点时，ptr2==NULL，在循环时需要注意。代码如下:
/**
* 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||!head->next)
return head;
struct ListNode dummy(0);
dummy.next = head;
struct ListNode *ptr1=&dummy,*ptr2=head;
while(ptr2){
if(!ptr2->next)
break;
struct ListNode * nextstart=ptr2->next->next;
ptr2->next->next=ptr2;
ptr1->next=ptr2->next;
ptr2->next=nextstart;
ptr1=ptr2;
ptr2=ptr2->next;
}
return dummy.next;
}
};