Swap Nodes in Pairs - leetcode

Swap Nodes in Pairs -- leetcode

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,借助临时变量作交换

在leetcode上执行时间为8ms。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        ListNode fake(0);
        ListNode *prev = &fake;

        while (head && head->next) {
                ListNode *bak = head->next->next;
                prev->next = head->next;
                head->next->next = head;
                prev = head;
                head = bak;
        }
        prev->next = head;

        return fake.next;
    }
};

写法二，

在写法一的基础上，去掉了临时变量bak。

此算法在leetcode上执行时间为12ms。

class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        ListNode fake(0);
        fake.next = head;
        ListNode *prev = &fake;

        while (head && head->next) {
                prev->next = head->next;
                head->next = head->next->next;
                prev->next->next = head;
                prev = head;
                head = head->next;
        }

        return fake.next;
    }
};

总结，算法2比算法1少用了一个临时变量。

个人更喜欢写法1,因为写法1的临时变量bak，编译器很容易用一个寄存器来表示。相比算法2,少了一次内存写访问操作。

这大概是写法1的执行时间比写法2更快的原因。