How do I swap nodes in pairs

Question

2.00/5 (1 vote)

See more:

I am solving leetcode problems and I can't figure out why my code is wrong. Here is the description of the 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.

And here is my code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
          if(head == null){
		   return null;
	   }
	   if(head.next == null){
		   return head;
	   }
	   
	   ListNode current = head;
	   ListNode temp = head.next;
	   head = head.next;
	   
	   while(temp != null){
		   current.next = temp.next;
		   temp.next = current;
		   current = current.next;
		   if(current == null)
		   {
			   return head;
		   }
		 temp = current.next;
		   
	   }
	   return head;
        
    }
}

it works in all cases, but in the following:

C#

Input:  {1,2,3,4}
Output: {2,1,3}
Expected:   {2,1,4,3}

Can anyone help me please? I would really appreciate any type of feedback

Posted 22-Oct-14 12:50pm

Alexander24

Add a Solution

Comments

Sergey Alexandrovich Kryukov 22-Oct-14 19:05pm

One word: debugger...
One note: "it works on all cases but one" is an apparently false statement; do I even have to explain why?
—SA

Alexander24 22-Oct-14 19:08pm

Probably you are right. But I have worked all the cases by hand and I was sure it works.

Sergey Alexandrovich Kryukov 22-Oct-14 20:02pm

Debugger...
—SA

Alexander24 22-Oct-14 20:04pm

I know that, I just did not want to write a whole program just to debug

Sergey Alexandrovich Kryukov 22-Oct-14 20:05pm

This statement makes no sense at all. Maybe you don't even know the meaning of the word "debugger", or something like that. You don't have to write anything. You want do debug you non-working code, not I. But if you think that "writing a whole program" is something bad, you probably need to change your profession. Can we stop this useless discussion?
—SA

Sergey Alexandrovich Kryukov 22-Oct-14 20:09pm

By the way, let me note that you did not even formulate the problem. It tells us what you should obtain only if the number of elements is even...
—SA

Philippe Mori 22-Oct-14 23:26pm

In that case, you only have to write about 5 simple lines of code to create a list and fill it with the 4 nodes. And a few more line for your main function.

Malcolm Chambers 22-Oct-14 20:44pm

First things First you don't need to write an entire program but you do need to write some tests, add a test solution to your project and then you can test fragments with out having to write an entire program. I have done that and developed some tests.

Secondly And as written the only case that work are 1 item in list and that is kind of suspect as it is undefined behavior.

Sergey Alexandrovich Kryukov 22-Oct-14 21:21pm

There is no such thing as "add solution to your project" (unless it is a special manually written "master project", not a C# project), there is a project added to a solution. But for this extremely simple problem, all testing can be done in the same project. OP already did that. Using the debugger simply means running the test under the debugger, doing appropriate stops on break points...
—SA

Malcolm Chambers 22-Oct-14 22:10pm

Yes I did put the words around the wrong way. This is the first time that I have been tempted to respond and provide my insight to a posted issue. Certainly when I tested his code I did only create a test project. I guess I was assuming (I know always a risk) that the code lived in a project, and that good practice is that you don't embed unit tests directly into any other project type.

3 solutions

Solution 1

I have written two helpers to make testing easy.

C#

private ListNode GenerateList(int GenerateTo)
{
  int i = 1;
  ListNode myList = new ListNode(i);
  ListNode Tail = myList;
  while (i < GenerateTo)
  {
    i++;
    ListNode newTail = new ListNode(i);
    Tail.next = newTail;
    Tail = Tail.next;
  }
  return myList;
}

And I have added a method to print the list as an additional method to the ListNode class

C#

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

   public string PrintList()
   {
     string result = string.Empty;
     if (next == null)
       result += string.Format("({0}) -> null", val);
     else
       result += string.Format("({0}) -> ", val) + next.PrintList();

     return result;
   }
 }

This made the tests very simple

C#

[TestMethod]public void TestMethod_Two()
    {
      ListNode testList = GenerateList(2);
      ListNode result = ClassUnderTest.swapPairs(testList);
      Assert.AreEqual("(2) -> (1) -> null", result.PrintList());
    }


    [TestMethod]
    public void TestMethod_One()
    {
      ListNode testList = GenerateList(1);
      ListNode result = ClassUnderTest.swapPairs(testList);
      Assert.AreEqual("(1) -> null", result.PrintList());
    }

My Suggestion that if you want this two work consider Regression as a solution.

Posted 22-Oct-14 14:51pm

Malcolm Chambers

Comments

PIEBALDconsult 22-Oct-14 23:39pm

"consider Regression as a solution"

I hope you don't mean recursion.

Solution 3

I finally fixed the problem. Here is my solution:

public class Solution {
    public ListNode swapPairs(ListNode head) {
      
      if(head == null){
		   return null;
	   }
	   if(head.next == null){
		   return head;
	   }
	   
	   ListNode temp = head.next;
	   ListNode current = head;
	   head = head.next;
	   ListNode prev = new ListNode(0);
	   
	  
	   while(temp != null){
		   current.next = temp.next;
		   temp.next = current;
		   prev.next = temp;
		   current = current.next;
		   if(current == null)
		   {
			   return head;
		   }
		   else
		       prev = temp.next;
			   temp = current.next;
		   
	   }
	   return head;
    }
}

Posted 23-Oct-14 7:22am

Alexander24

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Malcolm Chambers · Accepted Answer · 2014-10-22T18:04:00

Anyway had a chance to complete a solution that makes use of regression. To keep the logic clear I have probably created a few extra variables, but it wrote it to be clear in what it did. The advantage with this method that it only parses the list once so even with the extra variables it is vary efficient.

C#

public static ListNode swapPairsReg(ListNode List)
{
  if (List == null)
    return null;
  ListNode One = List;
  ListNode Two = One.next;

  if (Two == null)
    return One;
  ListNode tail = Two.next;

  ListNode NewList = Two;
  NewList.next = One;
  NewList.next.next = swapPairsReg(tail);
  return NewList;
}