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:
  5.     ListNode *swapPairs(ListNode *head) {
  6.         if (head == nullptr || head->next == nullptr) return head;
  7.         ListNode dummy(-1);
  8.         dummy.next = head;
  10.         for(ListNode *prev = &dummy, *cur = prev->next, *next = cur->next;
  11.                 next;
  12.                 prev = cur, cur = cur->next, next = cur ? cur->next: nullptr) {
  13.             prev->next = next;
  14.             cur->next = next->next;
  15.             next->next = cur;
  16.         }
  17.         return dummy.next;
  18.     }
  19. };

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

  1. // Swap Nodes in Pairs
  2. // 时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     ListNode* swapPairs(ListNode* head) {
  6.         ListNode* p = head;
  8.         while (p && p->next) {
  9.             swap(p->val, p->next->val);
  10.             p = p->next->next;
  11.         }
  13.         return head;
  14.     }
  15. };

相关题目

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