Problem
Given a linked list, swap every two adjacent nodes and return its head.
Example:
Given1->2->3->4, you should return the list as2->1->4->3.
Note:
- Your algorithm should use only constant extra space.
- You may not modify the values in the list’s nodes, only nodes itself may be changed.
Solution
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua class Solution { public: ListNode *swapPairs(ListNode *head) { if (!head || !head->next) return head; ListNode d(0); d.next = head; head = &d; while (head && head->next && head->next->next) { auto n1 = head->next; auto n2 = n1->next; n1->next = n2->next; n2->next = n1; head->next = n2; head = n1; } return d.next; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution: def swapPairs(self, head): if not head or not head.next: return head dummy = ListNode(0) dummy.next = head head = dummy while head.next and head.next.next: n1, n2 = head.next, head.next.next n1.next = n2.next n2.next = n1 head.next = n2 head = n1 return dummy.next |
Related Problems
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment