筆試題37. LeetCode OJ (24)

這個題的意思是將一個鏈表，按照每兩個節點逆序。我想了一下，主要是對鏈表的操作以及對指針的交換，掌握了方法以後確實不是很難，但是需要注意的是不要將指針給弄錯了，否則容易導致鏈表信息丟失。

我的方法中使用到了四個主要指針，我畫了個圖來解釋它們：

這四個指針的作用通過上圖，大家應該能夠理解了，因為我們需要做的事有三件：

（1）交換中間部分 (通過prev和cur)

（2）連接前面部分（通過pprev）

（3）連接後面部分（通過next）

代碼如下：

/**
 * 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 *Head = head->next;
        //四個指針
        //該指針指向交換部分的第一個節點
        ListNode *prev=head;
        //該指針指向交換部分的第二個節點
        ListNode *cur=head->next;
        //指向下一個需要的交換的部分，用於連接鏈表
        ListNode *next = cur->next;
        cur->next = prev;
        prev->next = NULL;
        //指向交換部分的前面的序列的末尾
        ListNode *pprev=prev;
        while(next)
        {
           prev = next;
           cur = prev->next;
           if(cur == NULL)
           {
               pprev->next = prev;
               break;
           }
           next = cur->next;
           cur->next = prev;
           prev->next = NULL;
           pprev->next=cur;
           pprev=prev;
        }
        return Head;
    }
};