24、Swap Nodes in Pairs
题目
看到此题,第一想法是利用两个指针,分别将其所指向的节点的value交换。然后同时向后移动2个节点,代码如下:
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
}; class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *first,*second;
if(NULL == head || NULL == head->next)//空或者只有一个节点
return head;
first = head;
second = head->next;
int temp;
while (NULL != second)
{
temp = first->val;
first->val = second->val;
second->val = temp; first = second->next;
if(NULL == first)
return head;
second = first->next;
if (NULL == second)
return head;
}
}
};
但是题目明确要求不能通过交换值的方式,只能对整个节点操作。因此在上面的代码中,需要利用一个指针指向second之后的节点,然后交换first和second,代码如下:
//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 *first,*second;
if(NULL == head || NULL == head->next)//空或者只有一个节点
return head;
first = head;
second = head->next;
ListNode *temp;
ListNode *pHead,*pre;
pHead = second;//虚头节点指向第二个节点,因为第二个节点在交换后会作为头结点;
while (NULL != second)
{
temp = second->next;
first->next = second->next;
second->next = first;
pre = first;
if(NULL == temp)
break;
first = temp; second = first->next;
if (NULL == second)
break;
pre->next = second;
}
head = pHead;
return head;
}
};
-------------------------------------------------------------------------------------------------分割线----------------------------------------------------------------------------
25、Reverse Nodes in k-Group
题目
这一题是24题的升级,如果解决了这一题,当k=2就是24题。因此该题更通用更具一般性。其解决方法是利用一个stack,依次将k个节点放入stack,代码如下:
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
}; class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if(k <= || NULL == head)
return head;
stack<ListNode*> myStack;
ListNode *pre,*tail,*current,*temp,*phead;
current = head;
int i;
tail = new ListNode(-);//构造一个伪头结点
phead = tail; while (NULL != current)
{
for (i=;i<k;i++)
{
if(current == NULL)//说明不够k节点
break;
pre = current;
current = current->next;
pre->next = NULL;
myStack.push(pre); }
if(i == k)
{
while(!myStack.empty())
{
temp = myStack.top();
myStack.pop();
tail->next = temp;//tail是当前已经交换好的链表的最后一个节点
tail = tail->next;
}
}
else//stack中不够k个节点,顺序不变
{
pre = NULL;
while(!myStack.empty())
{
temp = myStack.top();
myStack.pop();
temp->next = pre;
pre = temp;
}
tail->next = pre;
}
if(!flag)
{
head = phead->next;
flag = true;
}
} return phead->next;
}
};
因为代码中使用了栈,如果k比较大的话。辅助空间也是比较大的,并且在最后的翻转中,如果个数不足k个,是不需要翻转,而上面的代码需要先拆掉又重新链接起来,相当于做了无用功,因此改进实现如下(网上查找的代码):
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
ListNode *newHead = new ListNode();
newHead->next = head; int cnt = ;
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 = ;
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;
}
};