【leetcode hot 100 24】两两交换链表中的节点

解法一：先判断链表是否为空，若为空则直接返回；否则用left和right指向第一个和第二个节点，当这两个节点非空时一直执行交换。其中先判断right.next==null，说明链表为偶数且已经交换完break；再判断right.next.next==null，说明链表为奇数且已经交换完break；否则重新设置left和right继续循环。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {if (head == null){return head;}ListNode left=head, right=head.next;while(left!=null && right!=null){int temp = left.val;left.val = right.val;right.val = temp;if(right.next==null){break;}if(right.next.next==null){break;}left = right.next;right = left.next;}return head;}
}

注意：

• 先判断链表是否为空，若为空则直接返回
• 若left!=null && right!=null，则一直交换
• 先判断right.next==null，说明链表为偶数且已经交换完break；再判断right.next.next==null，说明链表为奇数且已经交换完break；否则重新设置left和right继续循环。

错误原因：只进行了节点内部值的交换，不是节点之间的交换。

解法二：递归

递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。

如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。

class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) {return head;}ListNode newHead = head.next;head.next = swapPairs(newHead.next);newHead.next = head;return newHead;}
}

注意：

• 中止条件：head == null || head.next == null