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

Question

我已将节点定义为

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

我在编写递归代码时遇到困难。迭代效果很好。这是我的代码。这个想法是检查列表是否为空。如果不存在，则检查第三个元素是否存在。如果是，则与其交换数据。然后转到下一个节点，即第四个节点。然后调用下一个节点的递归函数。我的想法有什么问题吗？

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

}

Answer 1

假设您只需要交换第一个和第三个节点的数据，保持节点列表本身不变，您可以尝试以下操作:

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