LeetCode - 24 Swap Nodes in Pairs

作者 QIFAN 日期 2016-07-16
LeetCode - 24 Swap Nodes in Pairs

Difficulty:Easy

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

For example, given 1->2->3->4, you should return the list as 2->1->4->3.

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

思路

这题和21 Merge Two Sorted List类似,只要不断的变reference就行,不需要创建新的对象。

  1. 递归时需要判断node.nextnode.next.next,即已到达最后节点和只剩一个节点时不用swap,直接return。
  2. 判断该节点是不是头节点,若不是则需要lastNode.next = node

代码

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null || head.next==null) return head;
ListNode newhead = head.next;
changePairs(head, null);
return newhead;
}
public void changePairs(ListNode l, ListNode last) {
if(l==null || l.next==null) return;
ListNode next = l.next;
l.next = next.next;
next.next = l;
if(last!=null) last.next = next;
changePairs(l.next, l);
}
}

原题链接:https://leetcode.com/problems/swap-nodes-in-pairs/