Problem
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.
Solution
type
ListNodeObj = object
val: int
next: ref ListNodeObj
ListNode = ref ListNodeObj
proc newListNode(val: int, next: ListNode = nil): ListNode =
result = ListNode(val: val, next: next)
proc swapPairs(head: ListNode): ListNode =
if head == nil or head.next == nil:
return head
let dummy = newListNode(0, head)
var p = dummy
while p.next != nil and p.next.next != nil:
var q = p.next.next
p.next.next = q.next
q.next = p.next
p.next = q
p = q.next
result = dummy.next
when isMainModule:
let
l1 = newListNode(1, newListNode(2, newListNode(3, newListNode(4))))
l2 = swapPairs(l1)
assert l2.val == 2 and
l2.next.val == 1 and
l2.next.next.val == 4 and
l2.next.next.next.val == 3 and
l2.next.next.next.next == nil
近期评论