24. Swap Nodes in Pairs
- Total Accepted: 130373
- Total Submissions: 354429
- Difficulty: Easy
- Contributors: Admin
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.
Code
# 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 node, the node before head
node_prev = ListNode(0)
node_prev.next = head
node_prev_bak = node_prev
while node_prev.next and node_prev.next.next:
node1, node2 = node_prev.next, node_prev.next.next
# doing the actual swap
node_prev.next = node2
node1.next = node2.next
node2.next = node1
node_prev = node1
return node_prev_bak.next
Idea
Very straightforward. Every time, you do the swapping on the two nodes.
Reference
https://discuss.leetcode.com/topic/18860/7-8-lines-c-python-ruby