方法一：递归
这次一定要记住递归三要素，不能改了：
1、终止条件
2、返回值
3、本级递归做什么
以后碰到这个题一定要用递归。
package test;
class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}
//class Solution {
// public ListNode swapPairs(ListNode head) {
// //终止条件
// if(head == null || head.next == null){
// return head;
// }
// //返回值
// head.next = swapPairs(head.next.next);
// head.next.next = head;//这里不能使用两级指针，因为两级之后可能为null，必须定义一个中间指针
// return head.next;
// }
//}
class Solution {public ListNode swapPairs(ListNode head) {if(head == null || head.next == null){//终止条件return head;}ListNode next = head.next;head.next = swapPairs(next.next);//返回值next.next = head;//本级递归做什么return next;}
}public class Main{public static void main (String []args){ListNode l1 = new ListNode(1);//@466ListNode l2 = new ListNode(2);//@467ListNode l3 = new ListNode(3);//@468ListNode l4 = new ListNode(4);//@469l1.next = l2;l2.next = l3;l3.next = l4;Solution p = new Solution();ListNode b = p.swapPairs(l1);while (b != null){System.out.print("->"+b.val);b = b.next;}}
}
方法二：迭代
也是先定义哑结点，然后指向头结点，让后面两个节点交换。然后prev移动，head移动。这种题最多定义三个结点，哑结点，移动结点，移动头结点。
package test;
class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}
class Solution {public ListNode swapPairs(ListNode head) {// Dummy node acts as the prevNode for the head node// of the list and hence stores pointer to the head node.ListNode dummy = new ListNode(-1);dummy.next = head;ListNode prevNode = dummy;while ((head != null) && (head.next != null)) {// Nodes to be swappedListNode firstNode = head;ListNode secondNode = head.next;// SwappingprevNode.next = secondNode;firstNode.next = secondNode.next;secondNode.next = firstNode;// Reinitializing the head and prevNode for next swapprevNode = firstNode;head = firstNode.next; // jump}// Return the new head node.return dummy.next;}
}public class Main{public static void main (String []args){ListNode l1 = new ListNode(1);//@466ListNode l2 = new ListNode(2);//@467ListNode l3 = new ListNode(3);//@468ListNode l4 = new ListNode(4);//@469l1.next = l2;l2.next = l3;l3.next = l4;Solution p = new Solution();ListNode b = p.swapPairs(l1);while (b != null){System.out.print("->"+b.val);b = b.next;}}
}