Swap Nodes in Pairs

描述

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.

分析

无

代码

  1. // Swap Nodes in Pairs
  2. // 时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4.     public ListNode swapPairs(ListNode head) {
  5.         if (head == null || head.next == null) return head;
  6.         ListNode dummy = new ListNode(-1);
  7.         dummy.next = head;
  9.         for(ListNode prev = dummy, cur = prev.next, next = cur.next;
  10.                 next != null;
  11.                 prev = cur, cur = cur.next, next = cur != null ? cur.next: null) {
  12.             prev.next = next;
  13.             cur.next = next.next;
  14.             next.next = cur;
  15.         }
  16.         return dummy.next;
  17.     }
  18. }

下面这种写法更简洁，但题目规定了不准这样做。

  2. // Swap Nodes in Pairs
  3. // 时间复杂度O(n)，空间复杂度O(1)
  4. class Solution {
  5.     public ListNode swapPairs(ListNode head) {
  6.         ListNode p = head;
  8.         while (p != null && p.next != null) {
  9.             int tmp = p.val;
  10.             p.val = p.next.val;
  11.             p.next.val = tmp;
  13.             p = p.next.next;
  14.         }
  16.         return head;
  17.     }
  18. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/linked-list/swap-nodes-in-pairs.html