24.两两交换链表中的节点
需要实际交换节点,而不是交换节点中的值。
1.递归 :
问题可以分解为:当前两个结点进行交换+剩余结点进行交换
可以使用递归方法。
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; // 当前头(第一个)称为新头.next (第二个) return newHead; }
//递归的另一种,可能更好理解一点
public ListNode swapPairs(ListNode head) { //终止条件 if (head == null || head.next == null) { return head; } ListNode newHead = head.next; ListNode rest = newHead.next; //前两个节点之后剩下的节点 newHead.next = head; head.next = swapPairs(rest); return newHead; }