将链接列表分成两部分，然后返回第二部分 [英] Divide a linked list into half and return the second half

问题描述

这是我做错的编程问题，部分代码如下:

This was a programming question that I did wrong.There was a partial code give as follows:

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.如果元素数为奇数，则多余的元素应该放在上半部分.我做不到.然后我的老师给出了如下答案:

My task was to create a method that divides the linked list in half leaving the first half of the elements in the original list and returning a new SingleLinkedList containing the second half of the list.If the number of elements is odd, then the extra element should go with the first half.I could not do it.Then my teacher gave answer like the following:

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

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

However, I'm not even getting the answer.I am a beginner.I would appreciate if someone can explain this problem.

推荐答案

您的老师提供的代码不完整.无论如何，我可以给您两种方法来找到下半部分的指针:

The code which you have provided by your teacher is incomplete. Anyways I can give you two ways to find the pointer to second half:

1. 如果要让指针引用同一列表的后半部分.

1. If you want a pointer to refer second half in the same list.

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

如果要创建下半部分所有节点的新列表，则可以执行以下操作:首先找到中间节点，然后通过创建新节点从下半部分创建新列表节点从中间节点迭代到列表的末尾.

If you want to create a new list with all the nodes in the second half, then you can do the following.Here first we find the middle node then we will create a new list from second half by creating new node iterating from middle node to the end of the list.

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

这篇关于将链接列表分成两部分，然后返回第二部分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！