[LeetCode]88. 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.

Subscribe to see which companies asked this question

 

解法：题目要求不能修改节点的值，因此只能调整节点的指针。每次调整两个节点，依次往前移动。

/**
 * 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) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* help = new ListNode(0);
        help->next = head;
        ListNode *first = help, *second = head, *third = head->next;
        while (third != NULL) {
            ListNode* tmp = third->next;
            third->next = first->next; // 调整一对节点
            first->next = third;
            second->next = tmp;
            if (tmp == NULL) break;
            first = second; // 前移到下一对节点
            second = tmp;
            third = tmp->next;
        }
        return help->next;
    }
};