這個題的意思是將一個鏈表,按照每兩個節點逆序。我想了一下,主要是對鏈表的操作以及對指針的交換,掌握了方法以後確實不是很難,但是需要注意的是不要將指針給弄錯了,否則容易導致鏈表信息丟失。
我的方法中使用到了四個主要指針,我畫了個圖來解釋它們:
這四個指針的作用通過上圖,大家應該能夠理解了,因為我們需要做的事有三件:
(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; } };