Mark As Completed Discussion

Good morning! Here's our prompt for today.

Description

Write a recursive algorithm that swaps every two nodes in a linked list. This is often called a pairwise swap. For example:

JAVASCRIPT
1/*
2original list
31 -> 2 -> 3 -> 4
4
5after swapping every 2 nodes
62 -> 1 -> 4 -> 3
7*/

You may assume that the definition of a linked list node is:

JAVASCRIPT
1function Node(val) {
2  this.value = val;
3  this.next = null;
4}

The method will be invoked as such after setup:

JAVASCRIPT
1const list = new Node(1);
2list.next = new Node(2);
3list.next.next = new Node(3);
4list.next.next.next = new Node(4);
5
6swapEveryTwo(list);

Constraints

  • Length of the linkedlist <= 100000
  • The nodes will always contain integer values between -1000000000 and 1000000000
  • The list can be empty
  • Expected time complexity : O(n)
  • Expected space complexity : O(n)

Note: The strength of linked lists is that you can dynamically add or remove any nodes within a constant time, given the address of the node. This is not possible in arrays or a sequential memory holding data structure. Each node in a linked list is created dynamically on the heap section of the memory. For this reason, you can create a very large Linked List (most probably larger than an array of the same size) as long as you have a memory to allocate. Creating more nodes than your memory can store will result in a heap overflow.

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

PYTHON
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

We'll now take you through what you need to know.

How do I use this guide?

Access all course materials today

The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.

Returning members can login to stop seeing this.