如何成对交换节点 [英] How do I swap nodes in pairs

问题描述

我正在解决leetcode问题，我无法弄清楚为什么我的代码出错了。以下是问题的描述：

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:

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

推荐答案

我写了两个助手来简化测试。

I have written two helpers to make testing easy.

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;
}

我添加了一个方法来打印列表作为ListNode类的附加方法

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

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

[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.

无论如何都有机会完成一个利用回归的解决方案。为了保持逻辑清晰，我可能已经创建了一些额外的变量，但它写了它以明确它做了什么。这种方法的优势在于它只解析列表一次，所以即使使用额外的变量也会有效。

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.

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;
}

我终于解决了这个问题。这是我的解决方案：

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;
    }
}

这篇关于如何成对交换节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！