两两交换链表中的节点
问题描述
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
输入说明
首先输入链表长度len，然后输入len个整数，以空格分隔。
输出说明
输出格式见范例
输入范例
4 1 2 3 4
输出范例
head–>2–>1–>4–>3–>tail
题解
完整代码
问题不难，完整代码及注释如下：
代码语言：javascript复制#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode() : val(0), next(NULL) {}
ListNode(int x) : val(x), next(NULL) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution
{
public:
ListNode* swapPairs(ListNode* head)
{
//填充本函数完成功能
ListNode* p=head,*q,*fade_head;
fade_head = new ListNode;
fade_head ->next =head;
ListNode *mark = fade_head;//direct to swap(p,q) 的前节点
//len
int len =0;
while(p)
{
len ;
p=p->next;
}
if(len >1)
{
//deal
p=head;
int tot=0;
while(p)
{
tot ;
if(tot == 2)//swap(p,q), 保证了q的存在
{
//swap(p,q)
mark->next =p;
q->next = p->next;
p->next = q;
//init
mark = q;
tot=0;
q=p;//前面 p、q节点换位置了
p=q->next;
}
//
q=p;
p=p->next;
}
}
head =fade_head->next;
return head;
}
};
ListNode *createByTail()
{
ListNode *head;
ListNode *p1,*p2;
int n=0,num;
int len;
cin>>len;
head=NULL;
while(n<len && cin>>num)
{
p1=new ListNode(num);
n=n 1;
if(n==1)
head=p1;
else
p2->next=p1;
p2=p1;
}
return head;
}
void displayLink(ListNode *head)
{
ListNode *p;
p=head;
cout<<"head-->";
while(p!= NULL)
{
cout<<p->val<<"-->";
p=p->next;
}
cout<<"tailn";
}
int main()
{
ListNode* head = createByTail();
head=Solution().swapPairs(head);
displayLink(head);
return 0;
}关于swap(p,q)的无效性讨论
p 、 q 为相邻节点
swap()的思想出现在下面函数中，
class Solution
{
public:
ListNode* swapPairs(ListNode* head)
{
//填充本函数完成功能
ListNode* p=head,*q,*fade_head;
fade_head = new ListNode;
fade_head ->next =head;
ListNode *mark = fade_head;//direct to swap(p,q) 的前节点
//len
int len =0;
while(p)
{
len ;
p=p->next;
}
if(len >1)
{
//deal
p=head;
int tot=0;
while(p)
{
tot ;
if(tot == 2)//swap(p,q), 保证了q的存在
{
//swap(p,q)
mark->next =p;
q->next = p->next;
p->next = q;
//init
mark = q;
tot=0;
q=p;//前面 p、q节点换位置了
p=q->next;
}
//
q=p;
p=p->next;
}
}
head =fade_head->next;
return head;
}
};其中的
q->next = p->next; p->next = q;
本想着用swap(p,q)直接偷懒，最后更新下p、q前一个结点的指向关系就ok，结果输出和输入一毛一样，原本还在纠结，p、q 交换后到底交换了什么？到底是p、q节点的内容变了，位置不变【p、q指向发生了变化】，还是内容不变，p、q位置变了【p、q节点位置发生了变化】，自嘲自己一下，交换指针我还是自己手写交换节点位置吧，交换后p、q的指向再换一下，这个思路还是熟悉的。
感受
链表题目的特殊操作，考虑的特例 空表、1、2，为什么要考虑2个节点呢？ 比如在节点向后尾插，可能当前操作节点和最后一个节点重叠，出bug。
