通过递归交换LinkedList中的每个第1和第3个元素数据

I have defined the node as

我已将节点定义为

class Node
{
    int data ;
    Node next ;
    Node(int data)
    {
        this.data = data ;
        next = null ;
    }
}

I am having difficulty writing the recursive code. The iterative works just fine. This is my code. The idea is to check if list is null. If not then check if 3rd element exists. If it does, swap data with it. Then go to the next node which is the 4th one. Then call recursive function for the next node. What is wrong with my idea ?

我在编写递归代码时遇到了困难。迭代工作得很好。这是我的代码。我们的想法是检查列表是否为空。如果没有，则检查是否存在第3个元素。如果是，请与它交换数据。然后转到下一个节点，即第4个节点。然后为下一个节点调用递归函数。我的想法出了什么问题？

public class change_1_and_3 {

Node head ;

Node changeUtil(Node head)
{
    Node temp = head ;
    if(head==null)
        return head ;
    if(temp.next.next!=null)
    {
        int res = temp.data ;
        temp.data = temp.next.next.data;
        temp.next.next.data = res ;
        temp = temp.next.next ;
    }
    else
        return head ;
    if(temp.next!=null)
        temp = temp.next ;
    else
        return head ;
    return changeUtil(temp);
}

void change()
{
    Node temp = changeUtil(head);
    while(temp!=null)
    {
        System.out.println(temp.data);
        temp = temp.next ;
    }
}

}

1 个解决方案

#1

Supposing you just need to swap the data of each 1st and 3rd node, leaving the list of nodes itself unchanged, you might try the following:

假设您只需要交换每个第1和第3个节点的数据，保持节点列表本身不变，您可以尝试以下方法：

Node changeUtil(Node head)
{
  // Ignore if not both the 1st and 3rd node exist
  // This is were your code fails!!
  if ((head == null) || (head.next == null) || (head.next.next == null))
    return (head);

  // Point to 3rd node
  Node third;
  third = head.next.next;

  // Swap contents
  int temp;
  temp = head.data;
  head.data = third.data;
  third.data = temp;

  // Same stuff starting from 4th node
  changeUtil(third.next);

  // Done
  return (head);

} // changeUtil