非递归方法(自己写的)
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null)
return head;
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy;
ListNode cur = head;
while (cur != null && cur.next != null) {
ListNode curNext = cur.next;
cur.next = curNext.next;
curNext.next = cur;
pre.next = curNext;
pre = cur;
cur = cur.next;
}
return dummy.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;
}
}
递归思路
1. 找终止条件
当递归到链表为空或链表中只剩一个元素时。没有可以交换的节点,就终止递归
2.找返回值
返回给上一层的值应该是已经交换完成之后的子链表
3.单次的过程
因为递归时重复做一样的事,从宏观上讲,只考虑某一部是怎么完成的。
假设待交换的两个节点分别是head和next,next应该接受上一级返回的子链表。
就相当于是一个含有三个节点的链表交换前两个节点。