首页 > 代码库 > 【LeetCode】Swap Nodes in Pairs (3 solutions)

【LeetCode】Swap Nodes in Pairs (3 solutions)

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.

 

解法一:递归

/** * 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* newhead = head->next;        head->next = swapPairs(newhead->next);        newhead->next = head;        return newhead;    }};

技术分享

 

解法二:Reverse Nodes in k-Group令k=2

/** * 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) {        return reverseKGroup(head,2);    }    ListNode *reverseKGroup(ListNode *head, int k) {        ListNode* newhead = new ListNode(-1);        ListNode* tail = newhead;        ListNode* begin = head;        ListNode* end = begin;        while(true)        {            int count = k;            while(count && end != NULL)            {                end = end->next;                count --;            }            if(count == 0)            {//reverse from [begin, end)                stack<ListNode*> s;                while(begin != end)                {                    s.push(begin);                    begin = begin->next;                }                while(!s.empty())                {                    ListNode* top = s.top();                    s.pop();                    tail->next = top;                    tail = tail->next;                }            }            else            {//leave out                tail->next = begin;                break;            }        }        return newhead->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) {        ListNode* newhead = new ListNode(-1);        newhead->next = head;        ListNode* cur = newhead;        while(cur->next != NULL && cur->next->next != NULL)        {            cur->next = reverse(cur->next, cur->next->next);            cur = cur->next->next;        }        return newhead->next;    }    ListNode* reverse(ListNode* n1, ListNode* n2)    {//swap two adjacent nodes, the latter is returned        n1->next = n2->next;        n2->next = n1;        return n2;    }};

技术分享

【LeetCode】Swap Nodes in Pairs (3 solutions)