java - 将链表分成两半并返回后半部分

Question

这是一道我做错的编程题，给出部分代码如下:

public class SingleLinkedList<E> {
   private Node<E> head;
   private int size = 0;

   private static class Node<E> {
     private E data;
     private Node<E> next;

     /** Creates a new node with a null next field
         @param dataItem  The data stored
     */
     private Node(E data) {
       data = dataItem;
       next = null;
     }

    /** Creates a new node that references another node
         @param dataItem  The data stored
         @param nodeRef  The node referenced by new node
     */
     private Node(E dataItem, Node<E> nodeRef) {
       data = dataItem;
       next = nodeRef;
     }
  }

}

我的任务是创建一个将链表分成两半的方法，将前半部分元素保留在原始列表中，并返回一个包含列表后半部分的新 SingleLinkedList。如果元素数量为奇数，则额外的元素应该放在前半部分。我做不到。然后我的老师给出了如下答案:

SingleLinkedList<E> newlist = new SingleLinkedList<E>();
 newlist.head =  temp.next; 
temp.next= null; 
return newlist

但是，我什至没有得到答案。我是初学者。如果有人能解释这个问题，我将不胜感激。

Answer 1

您老师提供的代码不完整。不管怎样，我可以给你两种方法来找到下半部分的指针:

1. 如果您想要一个指针来引用同一列表中的后半部分。

   private static Node getSecondHalfInSameList(Node head) {
       Node fastRunner = head, slowRunner = head;
       while(fastRunner != null && fastRunner.next != null) {
           slowRunner = slowRunner.next;
           fastRunner = fastRunner.next.next;
       }
       return slowRunner;
   }
   

2. 如果你想创建一个包含下半部分所有节点的新列表，那么你可以执行以下操作。这里首先我们找到中间节点然后我们将通过创建新的下半部分创建一个新列表从中间节点迭代到列表末尾的节点。

   private static Node getSecondHalfByCreatingNewNodes(Node head) {
       Node mid = getMiddleNode(head);
       Node newHead = new Node(mid.data);
       mid = mid.next;
       Node tail = newHead, temp;
       while(mid != null) {
           temp = new Node(mid.data);
           tail.next = temp;
           tail = temp;
       }
       return newHead;
   }
   
   private static Node getMiddleNode(Node head) {
       Node fastRunner = head, slowRunner = head;
       while(fastRunner != null && fastRunner.next != null) {
           slowRunner = slowRunner.next;
           fastRunner = fastRunner.next.next;
       }
       return slowRunner;
   }