三道很常见的面试题，Reorder List是一道完美洗牌题目，Rotate List是一道链表右转题目，Reverse Nodes in k-Group是链表分组反转题目，思路都比较清晰，考验代码基本功，涉及到指针的操作。
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}.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *findMid(ListNode *head) {//找出中间节点
ListNode *fast = head->next;
ListNode *slow = head;
while(fast != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
void merge(ListNode *&left,ListNode *&right){ //交替归并
ListNode *head = (ListNode *)malloc(sizeof(ListNode));
ListNode *res = head;
int cnt = 0;
while (left != NULL && right != NULL) {
if ((cnt & 1) == 0) {
head->next = left;
left = left->next;
} else {
head->next = right;
right = right->next;
}
head = head->next;
cnt ++;
}
if (left != NULL) {
head->next = left;
} else {
head->next = right;
}
left = res->next;
}
ListNode* reverseList(ListNode *head){ //链表反转
if(head == NULL || head->next == NULL){
return head;
}
ListNode *tail = head, *temp = NULL,*cur;
while(tail->next != NULL){
cur = tail->next;
tail->next = temp;
temp = tail;
tail = cur;
}
tail->next = temp;
return tail;
}
void createList(ListNode *&head){//创建链表
int x;
while(scanf("%d",&x) != EOF){
if(x == 0) break;
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->next = NULL;
node->val = x;
if(head == NULL) {
head = node;
} else {
node->next = head;
head = node;
}
}
}
void printList(ListNode *head){//打印
while(head != NULL){
cout<<head->val<<" ";
head = head->next;
}
cout << endl;
}
void reorderList(ListNode *head) {
if(head == NULL || head->next == NULL){
return;
}
ListNode *mid;
mid = findMid(head);
ListNode *tail = reverseList(mid->next);
mid->next = NULL; //将做半部分的尾指针设置为NULL
merge(head,tail);
}
};
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.
解题思路：首先将整个链表反转，然后分别找出左半部分和右半部分分别反转即可。
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *reverseList(ListNode *head) {
if(head == NULL || head->next == NULL) {
return head;
}
ListNode *tail = head, *temp = NULL,*cur;
while(tail->next != NULL) {
cur = tail->next;
tail->next = temp;
temp = tail;
tail = cur;
}
tail->next = temp;
return tail;
}
int ListLength(ListNode *head) {
if (head == NULL) {
return 0;
}
int cnt = 0;
while (head != NULL) {
head = head->next;
cnt ++;
}
return cnt;
}
ListNode *findKth(ListNode *head, int k) {
if(k == 0) {
return NULL;
}
ListNode *kthNode = head;
while(k > 1) {
kthNode = kthNode->next;
k --;
}
return kthNode;
}
ListNode *rotateRight(ListNode *head, int k) {
if(head == NULL || k == 0 || head->next == NULL) {
return head;
}
int length = ListLength(head);
k = k % length; //简单处理
head = reverseList(head);
ListNode *kthNode = findKth(head,k); //找到左半部分和右半部分
ListNode *right = NULL;
if(kthNode != NULL) {
right = reverseList(kthNode->next); //右半部分
kthNode->next = NULL;
}
ListNode *left = reverseList(head); //左半部分
ListNode *temp = left; //拼接到一起
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = right;
return left;
}
void createList(ListNode *&head){
int x;
while(scanf("%d",&x) != EOF){
if(x == 0) break;
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->next = NULL;
node->val = x;
if(head == NULL) {
head = node;
} else {
node->next = head;
head = node;
}
}
}
void printList(ListNode *head){
while(head != NULL){
cout<<head->val<<" ";
head = head->next;
}
cout << endl;
}
};
Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *reverseList(ListNode *head) { //反转
if (head == NULL || head->next == NULL) {
return head;
}
ListNode *tail = head, *temp = NULL, *cur;
while (tail->next != NULL) {
cur = tail->next;
tail->next = temp;
temp = tail;
tail = cur;
}
tail->next = temp;
return tail;
}
int ListLength(ListNode *head) { //计算链表长度
if (head == NULL) {
return 0;
}
int cnt = 0;
while (head != NULL) {
head = head->next;
cnt ++;
}
return cnt;
}
ListNode *ListAppend(ListNode *first, ListNode *second) {
if (first == NULL) {
first = second;
return first;
}
ListNode *res = first;
while (res->next != NULL) {
res = res->next;
}
res->next = second;
return first;
}
ListNode *reverseKGroup(ListNode *head, int k) {
if (k == 1 || k == 0 || head == NULL || head->next == NULL) {
return head;
}
int length = ListLength(head);
if(k > length) {
return head;
}//简单特例判断
ListNode *p = head;
ListNode *res = NULL;
while (p != NULL) {
int cnt = 1;
ListNode *temp = p;
while (cnt < k && temp != NULL) { //找到K个节点一组
cnt ++;
temp = temp->next;
}
if (temp == NULL) { //如果不够K，那么就直接拼接
res = ListAppend(res,p);
break;
}
ListNode *pnext = temp->next; //保留后续节点
temp->next = NULL;
ListNode *tail = reverseList(p);//反转当前K个节点
if (res == NULL) {
res = tail;
} else {
res = ListAppend(res, tail); //拼接
}
p = pnext; //恢复
}
return res;
}
void createList(ListNode *&head){
int x;
while(scanf("%d",&x) != EOF){
if(x == 0) break;
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->next = NULL;
node->val = x;
if(head == NULL) {
head = node;
} else {
node->next = head;
head = node;
}
}
}
void printList(ListNode *head){
while(head != NULL){
cout<<head->val<<" ";
head = head->next;
}
cout << endl;
}
};