小贝子编程

删除链表的最后一个节点



我正在练习使用链表节点，并且遇到了一个我不知道如何回答的问题。如何删除链表中的最后一个节点?下面的代码适用于所有条目栏的最后一个节点。最后一个不删除。

节点类
public class Node {
    private String data;
    private Node next;
    Node(String data, Node next)
    {
        this.data = data;
        this.next = next;
    }
    public void setData(String d)
    {
        data = d;
    }
    public void setNext(Node n)
    {
        next = n;
    }
    public String getData()
    {
        return data;
    }
    public Node getNext()
    {
        return next;
    }
主要

Node list = new Node("NODE 1",new Node("NODE 2",new Node("NODE 3", null)));
        list = insertSecond(list,"New Node");
        list = addLast(list,"LAST NODE");
        printList(list);
        System.out.println();
        deleteNode(list,"LAST NODE");
        printList(list);    
    }
    public static Node deleteNode(Node list,String str)
    {
        Node temp = list;
        Node prev = list;
        while(temp.getNext() != null)
        {
            if(temp.getData().equals(str))
            {
                if(prev.getNext() == null)
                    prev.setNext(null);
                else{
                prev.setNext(prev.getNext().getNext());
                }
            }
            prev = temp;
            temp = temp.getNext();
        }

while(temp != null){
  prev = temp;
  temp = temp.getNext();
}
prev.next = null;

试试这个:

这是我用来删除最后一个Node的非常简单的技术。

public void deleteLast() {
    Node curr = null;
    for (curr = this.first; curr.next.next != null;curr = curr.next) {
    }
    curr.next = null;
}

如果你使用双链列表，你的列表知道开始和结束，这是最简单的。

那么你可以这样做:

public void removeLastItem(){
    this.lastNode = this.lastNode.prev;
}

我猜while(temp.getNext() != null)对你的最后一个元素失败了。最后一个元素没有next元素。因此，最后一个元素不会与传递的字符串进行比较。您应该使用调试器来跟踪。

你需要这样做:

public static Node deleteNode(Node list, String str) {
  Node temp = list;
  Node prev = list;
  do {
    if (temp.getData().equals(str)) {
      if (prev.getNext() == null) {
        prev.setNext(null);
      } else {
        prev.setNext(prev.getNext().getNext());
      }
    }
    prev = temp;
    temp = temp.getNext();
  } while (temp != null);
  return list;
}

你太早停止循环了。

BTW: if (prev.getNext() == null) { prev.setNext(null); ...没有意义，但我会把这个bug留给你。

删除单链表中的节点

假设

  1. 列表中每个节点都有一个nextNode指针。
  2. headOfList指针指向列表中的第一个节点。
  3. 每个节点的下一个指针，已经在列表中，是正确的
  4. 列表中最后一个节点的下一个指针是某个有意义的值(例如，null)。

实现

的步骤
  1. 如果列表为空，则完成。
  2. 如果第一个节点是需要的节点，则将headOfList指针设置为headOfList->nextNode的值。完成了。找到所需节点
  3. 设置currentNode指针等于headOfList指针的值
  4. 如果currentNode节点是最后一个节点。完成了。
  5. 如果currentNode->nextNode为需要设置的节点，则将currentNode->nextNode设置为currentNode->nextNode->nextNode的值。完成了。找到所需节点
  6. 转到步骤4
指出

因为这是一个单链表，你不能备份。因此，您需要指向节点父节点并检查节点子节点是否是您希望删除的节点。会有边界条件。

的一些代码

这是LinkedList类的成员函数。startOfList是一个类成员，指向链表的起点。

 public boolean delete(final String target)
    {
        if (startOfList != null)
        {
            if (StringUtils.equals(startOfList.getData(), target))
            {
                startOfList = startOfList.getNext();
                return true;
            }
            Node current = startOfList;
            for (Node next = current.getNext(); next != null; next = current.getNext())
            {
                if (StringUtils.equals(next.getData(), target))
                {
                    current.setNext(next.getNext());
                    return true;
                }
                else // advance one node.
                {
                    current = next;
                }
            }
        }
        return false;
    }

这是我的尝试，假设最后一个节点的下一个变量将始终为null:

public class LastNodeRemoval {
  private static class Node {
      String item;
      Node next;
  }
  public static void main(String[] args) {
      Node third = new Node();
      third.item = "Third";
      Node second = new Node();
      second.item = "Second";
      second.next = third;
      Node first = new Node();
      first.item = "First";
      first.next = second;
      removalLastNode(first);
   }
   private static void removalLastNode(Node first) {
      Node temp = first;
      while(temp.next.next != null) {
          temp = temp.next;
      }
      temp.next = null;
      System.out.println("Last node: "+temp.item);
   }
}

这可以通过使用Java容器类"LinkedList"以更简单的方式完成。Java中的LinkedList类实现了Deque(双端队列)接口，该接口支持get/add/remove First/Last方法。下面是一个基本代码片段:

LinkedList<Integer> list = new LinkedList<Integer>();
list.addFirst(1);
list.addLast(2);
System.out.println(list.removeLast());

这个对我有用。

public void removeLastNode(){
    System.out.println("n Inside removeLastNode");
    next=firstLink;
    prev=firstLink;
    if(next == null) System.out.println("n The link List is Empty");
    while(next.getNext()!=null) { 
        prev=next;
        next=next.getNext();
    }
    prev.setNext(null);  
}

这里的逻辑很简单，它与获取最后一个节点相同。这里的棘手之处在于，当到达最后一个节点时，必须记住最后一个之前的节点，并将其设置为null，以便它将成为新的最后一个节点。在下面的代码中，当您到达最后一个元素n2时，获取n1并将其设置为null。

public void removeLast(){
    if(head==null) System.out.println("List is empty");
    else {
    Node n1 = null;
    Node n2 = head;
        while(n2.next != null)
        {
            n1 = n2;
            n2 = n2.next;
        }
        n1.next = null;
    }

public  Node deleteEnd(Node node)
{
if(node==null)
{
  throw new IllegalStateException();
}
    if(node.getNext()==null)
    return null;
    Node headF=node;
    while (node.getNext().getNext()!=null)
    {
        node=node.getNext();
    }
    node.setNext(null);
    return headF;
}

给定以下单链表实现，可以使用从first节点开始遍历列表的removeLast()或removeLastRecursive()方法删除最后一个节点:

public class LinkedList<T> {
    Node<T> first;
    Node<T> last;
    int length;
    public LinkedList() {
    }
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList();
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        linkedList.add("D");
        linkedList.printListParams();
        linkedList.removeLast();
        linkedList.printListParams();
        linkedList.removeLast();
        linkedList.printListParams();
        linkedList.removeLast();
        linkedList.printListParams();
        linkedList.removeLast();
        linkedList.printListParams();
        linkedList.removeLast();
        linkedList.printListParams();
    }
    public void add(T data) {
        if (isEmpty()) {
            first = new Node(data);
            last = first;
        } else {
            last.next = new Node(data);
            last = last.next;
        }
        length++;
    }
    public void removeLast() {
        Node current = first;
        if (isEmpty()) return;
        if (current.next != null) {
            while (current.next != null) {
                if (current.next.next == null) {
                    current.next = null;
                    last = current;
                    length--;
                    return;
                }
                current = current.next;
            }
        } else {
            first = null;
            last = null;
            length--;
        }
    }
    public void removeLastRecursive() {
        if (isEmpty()) return;
        if (first.next != null) {
            removeLast(first);
        } else {
            first = null;
            last = null;
            length--;
        }
    }
    private void removeLast(Node node) {
        if (node.next.next != null) {
            removeLast(node.next);
        } else {
            node.next = null;
            last = node;
            length--;
            return;
        }
    }
    public boolean isEmpty() {
        return first == null;
    }
    public void printList() {
        Node current = first;
        while (current != null) {
            System.out.print(current.data);
            current = current.next;
        }
        System.out.println();
    }
    public void printListParams() {
        printList();
        System.out.println("Length: " + length);
        System.out.println("Last node data: " + ((last != null) ? last.data : last));
        System.out.println("***********************");
    }
    private class Node<T> {
        T data;
        Node next;
        public Node(T data) {
            this.data = data;
        }
    }
}

/**
 * Deletion From End
 */
public static LinkedList DeletionFromEnd(LinkedList list){
    Node currNode = list.head;
    Node prevNode = null;
    while( currNode.getNext() != null) {
        prevNode = currNode;
        currNode = currNode.getNext();
    }
    prevNode.setNext(null);
    return list;
}

This Will Work:)

public void deleteFromLast()
{   Node secondLastNode=null;
    Node currentNode=first;
    while(currentNode.next!=null)
    {   secondLastNode=currentNode;
        currentNode=currentNode.next;
        if(currentNode.next==null)
        {
            secondLastNode.next=null;;
            break;
        }
    }
}
这更简单，更完美。
public void deleteLastNode() {
    Node curr = head;
    Node prevNode = null;
    if(head == null) return;
    while(curr != null && curr.next != null) {
        prevNode = curr;
        curr = curr.next;
    }
    if(head.next != null) prevNode.next = null;
    else head = null;
}

相关内容

  • 没有找到相关文章

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium