Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
题目
给一个链表，把其相邻两个元素交换位置。
思路1：递归
思考递归分三步：
- 递归终止条件，也可以理解为最小样本情况
- 自己调用自己
- 返回一个处理后的值
回到这个题目，终止条件，那就是当节点为空或者节点的next为空时，他就不用交换了，返回它自己就行了；
当节点不为空时，交换节点和其后面的节点，那么第二个节点的next应该连接到，第三个和第四个节点交换后的前面的节点，那么递归就产生了。
返回值也就是，返回交换后的前面的节点。
代码
public ListNode swapPairs3(ListNode head) {
if (head==null||head.next==null) {//递归终止条件
return head;
}
ListNode res = head.next;//返回的节点，即交换后在前面的节点
ListNode tmp =head.next.next;
head.next.next=head;//交换位置
head.next=swapPairs(tmp);//递归调用
return res;//返回交换后的位于前面的节点
}
思路2
我们不递归的话，就肯定需要几个指针来完成交换。
这里我们用三个指针，pre、cur、next；
pre：头结点的前驱
cur:头结点
next：头结点next的next
操作过程：
操作过程
代码
public ListNode swapPairs(ListNode head) {
if (head==null||head.next==null) {
return head;
}
ListNode preH =new ListNode(-1);
preH.next=head;
ListNode pre=preH;
ListNode cur=head;
ListNode next=null;
while (cur!=null&&cur.next!=null) {
next=cur.next.next;
pre.next=cur.next;
cur.next.next=cur;
cur.next=next;
pre=cur;
cur=next;
}
return preH.next;
}
