Java code example to implement reverse linked list

This article mainly introduces the code example of implementing reverse linked list in Java language. The editor thinks it is quite good. I share it with you here for the reference of friends who need it.

Problem description

Define a function that inputs the head node of a linked list, reverses the linked list and outputs the head node of the reversed linked list. The linked list nodes are as follows:

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

Idea 1:

To reverse the linked list, for node i, we need to Its next points to its predecessor, so we need to save the predecessor node. At the same time, if we have reassigned the next of i, we will not be able to find the successor of i. Therefore, before reassigning, we need to save the successor of i. .

Code:

public ListNode ReverseList(ListNode head) {
    if(head == null){
      return null;
    }
    ListNode rHead = null;
    ListNode prior = null;//store prior
    ListNode q = head;//store current
    while(q != null){
      ListNode next = q.next;//store the next
      if(next == null){
        rHead = q;
      }
      q.next = prior;
      prior = q;
      q = next;
    }
    return rHead;
  }

Idea 2:

Use the idea of ​​recursion (I haven’t thought of it yet, because if Using recursion, each time it should be: the first node of the linked list - the tail pointer of the linked list returned by recursion, but in this case, the reversed head pointer cannot be obtained.) Let’s think about it later.

Summarize

The above is the detailed content of Java code example to implement reverse linked list. For more information, please follow other related articles on the PHP Chinese website!