www.fatihkabakci.com

Personal Website and Computer Science TUR EN

Interview Question Swap Nodes in Pairs

Last update: 1/9/2017 12:02:00 AM

By Fatih KABAKCI

The problem is to swap each consecutive two nodes and return the same linked list.

Problem #24 - Swap Nodes in Pairs

Description: 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.

Difficulty: Easy

Solution in Java

head: {1		2		3	 	4}
root -> 1 2 3 4
r = root -> 1 2 3 4

while(r-next != null and r->next->next != null)
START CYCLE 0
	n = r->next;
		Then n : {1 2 3 4}, r -> {1 2 3 4}, root -> {1 2 3 4}
	p = r->next->next;
		Then p : {2 3 4}, r -> {1 2 3 4}, root -> {1 2 3 4}
	n->next = p->next; 
		Then n : {1 3 4}, r -> {1 3 4}, root -> {1 3 4}
	p->next = n;
		Then p : {2 1 3 4}, r -> {1 3 4}, root -> {1 3 4}
	r->next = p;
		Then r -> {2 1 3 4}, root -> {2 1 3 4}
	r = r.next.next;
		Then r : {1 3 4}, root -> {2 1 3 4}
END CYCLE 0
START CYCLE 1
	n = r->next;
		Then n : {3 4}, r : {1 3 4}, root -> {2 1 3 4}
	p = r->next->next;
		Then p : {4}, r : {1 3 4}, root -> {2 1 3 4}
	n->next = p->next; 
		Then n : {3 null}, r : {1 3}, root -> {2 1 3 4}
	p->next = n;
		Then p : {4 3 null}, r : {1 3}, root -> {2 1 3 4}
	r->next = p;
		Then r : {1 4 3 null}, root -> {2 1 4 3}
	r = r.next.next;
		Then r : {3, null}
END CYCLE 1
end while

package com.fatihkabakci.Easy.SwapNodesinPairs;
/**
 * @author fkabakci
 * 
 * Problem Description: 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:
 * 
 * When head is {1, 2, 3, 4}
 * 
 * 1. Define an empty node and then connect its next to the head.
 * 	  root -> {1, 2, 3, 4}
 * 
 * 2. Copy of root node.
 * 	  r -> {1, 2, 3, 4}
 * 
 * 3. Start with first two nodes. 
 * 	  r -> {1, 2, 3, 4}
 *              n  p
 * 4. Swap them.
 * 	  a. Connect next of p to next of n.
 *        b. Connect n to next of p.
 *        c. Connect p to next of r to keep r updated.
 * 
 * 5. Skip two nodes.
 */

public class SwapNodesinPairs {
	public ListNode swapPairs(ListNode head) {
		ListNode root = new ListNode(0);
		root.next = head;
	    ListNode r = root;
        while(r.next != null && r.next.next != null) {
			ListNode n = r.next;
			ListNode p = r.next.next;
			n.next = p.next;
			p.next = n;
			r.next = p;
			r = r.next.next;
        }
        return root.next;
    }
	
	public static void main(String[] args) {
		SwapNodesinPairs r = new SwapNodesinPairs();
		ListNode head = Data.init(new int[]{1, 2, 3, 4});
		ListNode entire = r.swapPairs(head);
		while(entire != null) {
			System.out.print(entire.val + " ->");
			entire = entire.next;
		}
	}
}

Similar Problems

MemberCommentDate:
Fatih KABAKCI
	
ListNode and the helper class Data which is used to initialize linked list are below.

public class ListNode {
	int val;
	ListNode next;
	ListNode(int x) {
		val = x;
	}
}

package com.fatihkabakci.Easy.RemoveNthNodeFromEndofList;

public class Data {
	public static ListNode init(int[] data) {
		ListNode head = new ListNode(data[0]);
		ListNode t = head;
		for(int i = 1; i < data.length; i++) {
			t.next = new ListNode(data[i]);
			t = t.next;
		}
		return head;
	}
}
1/8/2017 11:26:00 PM

Name:


Question/Comment
   Please verify the image




The Topics in Computer Science

Search this site for





 

Software & Algorithms

icon

In mathematics and computer science, an algorithm is a step-by-step procedure for calculations. Algorithms are used for calculation, data processing, and automated reasoning.

Programming Languages

icon

A programming language is a formal constructed language designed to communicate instructions to a machine, particularly a computer. It can be used to create programs to control the behavior of a machine. Java,C, C++,C#

Database

icon

A database is an organized collection of data. The data are typically organized to model aspects of reality in a way that supports processes requiring information.

Hardware

icon

Computer hardware is the collection of physical elements that constitutes a computer system. Computer hardware refers to the physical parts or components of a computer such as the monitor, memory, cpu.

Web Technologies

icon

Web development is a broad term for the work involved in developing a web site for the Internet or an intranet. Html,Css,JavaScript,ASP.Net,PHP are one of the most popular technologies. J2EE,Servlet, JSP,JSF, ASP

Mobile Technologies

icon

Mobile application development is the process by which application software is developed for low-power handheld devices, such as personal digital assistants, enterprise digital assistants or mobile phones. J2ME

Network

icon

A computer network or data network is a telecommunications network that allows computers to exchange data. In computer networks, networked computing devices pass data to each other along data connections.

Operating Systems

icon

An operating system is software that manages computer hardware and software resources and provides common services for computer programs. The OS is an essential component of the system software in a computer system. Linux,Windows

Computer Science

icon

Computer science is the scientific and practical approach to computation and its applications.A computer scientist specializes in the theory of computation and the design of computational systems.