24. 两两交换链表中的节点
问题描述
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
问题分析
开始我们新增一个节点ans,让它的下一个节点为head,为了描述简单，我们新设了四个节点a,b,c,d来辅助我们理解,这四个节点满足a->b->c->d(d是c的下一个节点),开始a代表新增的节点ans,不参与交换，只考虑b和c的交换，我们将a的next指向c（a->next = c）,这时a与b就断了: a->c->d, b。 再将b指向c的下一个节点（b->next = c->next）,这时有a->c->d, b->d,再将c和d连起来就完成b和c的互换（c->next = b):a->c->b->d.这时我们再将a指向将要换的下一个节点（d）的前一个节点(b),即a = a->next->next,再帮助d和d->next完成互换。所以a全程起一个辅助作用。
代码
/**
* 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* ans = new ListNode(0);
ListNode *a,*b,*c;
ans->next = head;
a = ans;
while(a->next != NULL && a->next->next != NULL)
{
b = a->next;
c = b->next;
a->next = c;
b->next = c->next;
c->next = b;
a = a->next->next;
}
b = ans->next;
delete ans;
return b;
}
};
25. K 个一组翻转链表
问题描述
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例 :
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明 :
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
问题分析
这个可以看做上一题的一般形式，不过需要先求出链表的长度，然后分组进行反转。这里反转的顺序和上一道题也不大一样，假设有a->b->c->d,先将b指向d,a->b->d,c,再将c指向b,a->b->d,c->b->d,再将a指向c,a->c->b->d,在反转完后需要对a,b重新赋值，此时a->...->c->b->d,因为a是头结点不变的，b是反转后的最后一个节点，是最后一个不变的节点，因此将b赋值给a,b指向b的下一个节点。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* ans = new ListNode(0);
ListNode *a,*b,*c;
int time=0;
ans->next = head;
a = ans;
b = head;
while(head)
{
head = head->next;
++time;
}
time /= k;
for(int i = 0; i < time; i++)
{
int j = 1;
while(j++ < k)
{
c = b->next;//c为即将插到a和b之间的节点
b->next = c->next;//因为b和c马上就要断开，b->next失效了可以利用
c->next = a->next;
a->next = c;
}
a = b;
b = a->next;
}
b = ans->next;
delete ans;
return b;
}
};