1721_SwappingNodesinaLinkedList - a920604a/leetcode GitHub Wiki

---

title: 1721. Swapping Nodes in a Linked List tags: - Linked List categories: leetcode comments: false

problem

solution

option 1 - 複寫值

/**
 * 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* swapNodes(ListNode* head, int k) {
        ListNode *slow = new ListNode(-1);
        ListNode *fast = slow;
        ListNode * t =slow;
        slow->next = head;
        int n = k;
        while(n--)
        {
            fast = fast->next;
        }
        while(fast->next) {
            slow=slow->next;
            fast=fast->next;
        }
        ListNode *last = slow->next;
        ListNode *first = t;
        while(k--){
            first =first->next;
        }
        int val = last->val;
        last->val = first->val;
        first->val = val;
        return t->next;
        
    }
};

option 2 - 交換節點

class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {
        if(!head || !head->next) return head;
        int size = 0;
        for(ListNode *p = head;p;p=p->next) size++;
        int a = k, b = size-k;
        ListNode *l = head , *r = head ;
        ListNode *pl = new ListNode(-1), *pr = pl, *ans = pl; 
        pl->next = head;
        a--;
        int la = min(a, b);
        int lb = max(a,b);
        while(la--) {
            pl = l;
            l=l->next;
        }
        while(lb--) {
            pr = r;
            r = r->next;
        }
        // edge case
        if(l->next ==r ){
            // pr == l
            l->next = r->next;
            pl->next = r;
            r->next = l;
            
            return ans->next;    
        }
        
        ListNode *rlast = nullptr;
        if(r->next) rlast = r->next;
        r->next= l->next;
        l->next = rlast;
        pl->next = r;
        pr->next = l;
        return ans->next;
    }
};

analysis

• time complexity O(n)
• space complexity O(1)