[LeetCode][Java] Swap Nodes in Pairs

题目:

Given a linked list, swap every two adjacent nodes and return its head.

For example,Given1->2->3->4, you should return the list as2->1->4->3.

Your algorithm should use only constant space. You maynotmodify the values in the list, only nodes itself can be changed.

题意：

给定一个单链表，交换链表中每两个相邻的元素，并返回新的链表的头结点。

比如：

给定1->2->3->4，你需要返回的新的链表为2->1->4->3.

你的算法只能用常数空间。你不能改变链表中结点的值，只能改变结点指针。

算法分析：方法一：

常规的链表题，做法也是常规的指针变换。最好事先自己在纸上画一下指针，指针变化稍复杂。

自己的AC代码如下。

AC代码：

//就是各种改指针public class Solution {public ListNode swapPairs(ListNode head){if(head==null||head.next==null) return head;int nums=0;ListNode testhead=head;while(testhead!=null){testhead=testhead.next;nums++;}ListNode p1,p2,p3,newhead,fpointer,spointer,ffpointer;p1=head;p2=head.next;p3=p2.next;p2.next=p1;p1.next=p3;newhead=p2;if(p1.next==null||p1.next.next==null) return newhead;ffpointer=p1;p1=p1.next.next;p2=p2.next.next;fpointer=p2;spointer=p1;while(p1!=null&&p2!=null){p1=fpointer;p2=spointer;p3=p2.next;//先保留第二个元素后面的链表中的剩余元素p2.next=p1;//指针交换p1.next=p3;ffpointer.next=p2;//第一个元素前面的元素所指，，最初是指向p1,在p1和p2互换后就指向p2了fpointer=p2;spointer=p1;if((nums%2==0&&spointer.next==null)||(nums%2!=0&&fpointer.next.next==null))break;p2=p2.next.next;p1=p1.next.next;fpointer=p2;spointer=p1;ffpointer=ffpointer.next.next;}return newhead;}}

方法二：思路：肯定是递归方便啦，我们做好了base case，一直调用自己就可以了。

别人家的代码：

public ListNode swapPairs(ListNode head){if(head==null) return null;if(head.next==null) return head;ListNode temp=head.next;ListNode forward=head.next.next;temp.next=head;head.next=swapPairs(forward);return temp;}}

唯有讲述此间途经的美景，分享没有男主角的相片。