24、Swap Nodes in Pairs
题目
看到此题，第一想法是利用两个指针，分别将其所指向的节点的value交换。然后同时向后移动2个节点，代码如下：
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 class Solution { 8 public: 9 ListNode* swapPairs(ListNode* head) {10 ListNode *first,*second;11 if(NULL == head || NULL == head->next)//空或者只有一个节点12 return head;13 first = head;14 second = head->next;15 int temp;16 while (NULL != second)17 {18 temp = first->val;19 first->val = second->val;20 second->val = temp;21 22 first = second->next;23 if(NULL == first)24 return head;25 second = first->next;26 if (NULL == second)27 return head;28 }29 }30 }; 但是题目明确要求不能通过交换值的方式，只能对整个节点操作。因此在上面的代码中，需要利用一个指针指向second之后的节点，然后交换first和second，代码如下：
1 //Definition for singly-linked list. 2 struct ListNode { 3 int val; 4 ListNode *next; 5 ListNode(int x) : val(x), next(NULL) {} 6 }; 7 8 class Solution { 9 public:10 ListNode* swapPairs(ListNode* head) {11 ListNode *first,*second;12 if(NULL == head || NULL == head->next)//空或者只有一个节点13 return head;14 first = head;15 second = head->next;16 ListNode *temp;17 ListNode *pHead,*pre;18 pHead = second;//虚头节点指向第二个节点，因为第二个节点在交换后会作为头结点；19 while (NULL != second)20 {21 temp = second->next;22 first->next = second->next;23 second->next = first;24 pre = first;25 if(NULL == temp)26 break;27 first = temp;28 29 second = first->next;30 if (NULL == second)31 break;32 pre->next = second;33 }34 head = pHead;35 return head;36 }37 };
-------------------------------------------------------------------------------------------------分割线----------------------------------------------------------------------------
25、Reverse Nodes in k-Group
题目
这一题是24题的升级，如果解决了这一题，当k=2就是24题。因此该题更通用更具一般性。其解决方法是利用一个stack，依次将k个节点放入stack，代码如下：
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 class Solution { 8 public: 9 ListNode* reverseKGroup(ListNode* head, int k) {10 if(k <= 1 || NULL == head)11 return head;12 stack myStack;13 ListNode *pre,*tail,*current,*temp,*phead;14 current = head;15 int i;16 tail = new ListNode(-1);//构造一个伪头结点17 phead = tail;18 19 while (NULL != current)20 {21 for (i=0;i next;27 pre->next = NULL;28 myStack.push(pre);29 30 }31 if(i == k)32 {33 while(!myStack.empty())34 {35 temp = myStack.top();36 myStack.pop();37 tail->next = temp;//tail是当前已经交换好的链表的最后一个节点38 tail = tail->next;39 }40 }41 else//stack中不够k个节点，顺序不变42 {43 pre = NULL;44 while(!myStack.empty())45 {46 temp = myStack.top();47 myStack.pop();48 temp->next = pre;49 pre = temp;50 }51 tail->next = pre;52 }53 if(!flag)54 {55 head = phead->next;56 flag = true;57 }58 }5960 return phead->next;61 }62 }; 因为代码中使用了栈，如果k比较大的话。辅助空间也是比较大的，并且在最后的翻转中，如果个数不足k个，是不需要翻转，而上面的代码需要先拆掉又重新链接起来，相当于做了无用功，因此改进实现如下（网上查找的代码）：
class Solution {public: ListNode *reverseKGroup(ListNode *head, int k) { ListNode *newHead = new ListNode(0); newHead->next = head; int cnt = 0; ListNode *cur_node = head; ListNode *last_tail = newHead; while(cur_node) { cnt++; if(cnt == k) { ListNode *cp = cur_node->next; cur_node->next = NULL; last_tail = reverseList(last_tail->next, last_tail); last_tail->next = cp; cur_node = cp; cnt = 0; continue; } cur_node = cur_node->next; } return newHead->next; } ListNode *reverseList(ListNode*head, ListNode*last_tail) { ListNode *next_node = head->next; ListNode *res = head; while(next_node) { ListNode *tmp = next_node->next; next_node->next = head; head = next_node; next_node = tmp; } last_tail->next = head; return res; }};