在Java中实现反转单链表

x33g5p2x  于2022-09-14 转载在 Java  
字(1.0k)|赞(0)|评价(0)|浏览(167)

反转单链表

反转单链表。

例子:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

在 Java 中实现反转单链表

要反转单个 LinkedList,我们可以保留两个指针 - 一个指向 currentNode,另一个指向前一个节点。 现在,我们可以迭代 LinkedList,并且对于每次迭代 -

  1. currentNode.next 指向 prevNode
  2. prevNode 移动到 currentNode
    1.将currentNode移动到LinkedList中的nextNode

这是完整的解决方案:

class ListNode {
  int val;
  ListNode next;
  ListNode(int val) {
    this.val = val;
  }
}

class ReverseLinkedListExample {

  private static ListNode reverseLinkedList(ListNode head) {
    ListNode prevNode = null;
    ListNode currentNode = head;
    
    while(currentNode != null) {
        ListNode nextNode = currentNode.next;
        currentNode.next = prevNode;
        prevNode = currentNode;
        currentNode = nextNode;
    }
    return prevNode;
  }

  public static void main(String[] args) {
    ListNode node = new ListNode(1);
    node.next = new ListNode(2);
    node.next.next = new ListNode(3);
    node.next.next.next = new ListNode(4);
    node.next.next.next.next = new ListNode(5);


    ListNode rNode = reverseLinkedList(node);
    while(rNode != null) {
      System.out.print(rNode.val + " ");
      rNode = rNode.next;
    }
    System.out.println();
  }
}
# Output
$ javac ReverseLinkedListExample.java
$ java ReverseLinkedListExample
5 4 3 2 1

相关文章

微信公众号

最新文章

更多