Given a linked list, swap every two adjacent nodes and return its head.
- Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
Example:
- Given
1->2->3->4, you should return the list as2->1->4->3.
C Solution:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head) {
struct ListNode **p = &head;
while (*p && (*p)->next) {
struct ListNode *right = (*p)->next;
(*p)->next = right->next;
right->next = *p;
*p = right;
p = &((*p)->next->next);
}
return head;
}
Recursive:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head) {
if (!head || !head->next) return head;
struct ListNode *tmp = head->next;
head->next = swapPairs(head->next->next);
tmp->next = head;
return tmp;
}
Python Solution 1:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next: return head
new_head = head.next
head.next, new_head.next = self.swapPairs(new_head.next), head
return new_head
Python Solution 2:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummy = ListNode(0)
dummy.next = head
cur = dummy
while cur.next and cur.next.next:
a = cur.next
b = a.next
cur.next, a.next, b.next = b, b.next, a
cur = a
return dummy.next
Summary:
- The first and second: 3ms, 0%.
- The second is much more readable. But it does't use constant space. Recursive is not O(1) space complexity.
- I prefer the first one, here I can use dummy head, too, pointer-pointer is more concise.
LeetCode: 24. Swap Nodes in Pairs
近期评论