1. 首頁 > 生活 > >

【算法訓練營day4】LeetCode24. 兩兩交換鏈表中的結點

生活百科

【算法訓練營day4】LeetCode24. 兩兩交換鏈表中的結點 LeetCode19. 刪除鏈表的倒數第N個結點 LeetCode面試題 02.07. 鏈表相交 LeetCode142. 環形鏈表IILeetCode24. 兩兩交換鏈表中的節點題目鏈接：24. 兩兩交換鏈表中的節點
初次嘗試比較暴力的解法，利用三個指針，進行類似反轉鏈表里面的反轉next指針指向的操作，然后三個指針整體向后移動到下一組節點，暴力但是ac 。
/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode() : val(0), next(nullptr) {} *     ListNode(int x) : val(x), next(nullptr) {} *     ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {public:    ListNode* swapPairs(ListNode* head) {        if (head == NULL || head -> next == NULL) return head;        ListNode* pre = head;        ListNode* cur = head -> next;        ListNode* temp = cur -> next;        head = head -> next;        while (true) {            cur -> next = pre;            pre -> next = temp;            if (temp != NULL && temp -> next != NULL) {                cur = temp -> next;                pre -> next = cur;                pre = temp;                temp = cur -> next;            }            else break;        }        return head;    }};看完代碼隨想錄后的想法思路差不多，忘記用虛擬頭結點了，重新用虛擬頭結點寫了一下，ac 。
【【算法訓練營day4】LeetCode24. 兩兩交換鏈表中的結點】/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode() : val(0), next(nullptr) {} *     ListNode(int x) : val(x), next(nullptr) {} *     ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {public:    ListNode* swapPairs(ListNode* head) {        if (head == NULL || head -> next == NULL) return head;        ListNode* dummyHead = new ListNode(0, head);        ListNode* cur = dummyHead;        while (cur -> next != NULL && cur -> next -> next != NULL) {            ListNode* temp1 = cur -> next;            ListNode* temp2 = cur -> next -> next;            cur -> next = temp2;            temp1 -> next = temp2 -> next;            temp2 -> next = temp1;            cur = cur -> next -> next;        }        return dummyHead -> next;    }};

經驗總結擴展閱讀