首页 > itarticle > [nim4leetcode] 24. swap nodes in pairs

[nim4leetcode] 24. swap nodes in pairs

admin 11月 13, 2020 0

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