Skip to content

24 Swap Nodes in Pairs ✅

Given a linked list, swap every two adjacent nodes and return its head.

Example:

Given 1->2->3->4, you should return the list as 2->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.

alt

Ideas

Set a dummy node to simplify the operation, dummy next points to head.

  • Initialize first as the first node
  • Initialize second as the second node
  • Initialize current to dummy
  • first.next = second.next
  • second.next = first
  • current.next = second
  • current move two grids
  • repeat

alt

Solution

Time complexity: \(O(n)\) Space complexity: \(O(1)\)

C# Solution (with two pointers)

namespace Algorithms.Medium
{

  /* // Definition for singly-linked list.
  public class ListNode
  {
    int val;
    ListNode next; ListNode(int x) { val = x; }
  } */

  public class SwapPairs
  {
    public ListNode Swap(ListNode head)
    {
      if (head == null || head.next == null) return head;

      var tempNode = new ListNode(-1);
      tempNode.next = head;
      head = tempNode;

      while (head != null && head.next != null && head.next.next != null)
      {
        var n1 = head.next;
        var n2 = n1.next;

        n1.next = n2.next;
        n2.next = n1;

        head.next = n2;
        head = n1;
      }

      return tempNode.next;
    }
  }
}

Version from Ideas

public ListNode Swap(ListNode head)
    {
      ListNode fakeHead = new ListNode(-1);
      fakeHead.next = head;
      ListNode node = fakeHead;

      while (node != null && node.next != null && node.next.next != null)
      {
        ListNode first = node;
        ListNode second = node.next;
        ListNode third = node.next.next;

        first.next = third;
        second.next = third.next;
        third.next = second;
        node = second;
      }

      return fakeHead;
    }
  }
    1. Sort List
    1. Remove Linked List Elements