Java implements sample code sharing for outputting the k-th node from the bottom of a linked list

This article mainly introduces the relevant content of the kth node from the bottom of the Java output linked list, involving three design ideas and code examples. It has certain reference value. Friends who need it can learn more.

Problem description

Input a linked list and output the k-th node from the last in the linked list. (The last node is the last one)

The node is defined as follows:

public class ListNode {
  int val;
  ListNode next = null;

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

Idea 1:

First traverse the linked list and calculate its length;
Then calculate that the kth node from the last is the positive length - k + 1.
Finally traverse the linked list and find what you want Node
has a time complexity of O(2n) and needs to traverse the linked list twice.

The code is as follows:

##

public ListNode FindKthToTail(ListNode head,int k) {
    if(head == null || k <= 0){
      return null;
    }
    //直接遍历
    ListNode p = head;
    int length = 1;
    while(p.next != null){
      length++;
      p = p.next;
    }
    int index = length - k + 1;
    if(index <= 0){
      return null;
    }
    p = head;
    int num = 1;
    while(p.next != null && num < index){
      num++;
      p = p.next;
    }
    if(num < index){
      return null;
    }else{
      return p;
    }
  }

Idea 2:

Expect to get it by traversing the linked list only once.

Set two pointers, one initialized to point to the first node, and the second to the k-th node. Then the two pointers move backward synchronously. When the second pointer points to the tail node, the first pointer points to the k-th node from the bottom

Code:

public ListNode FindKthToTail(ListNode head,int k) {
    if(head == null || k <= 0){
      return null;
    }
    //直接遍历
    ListNode p = head;
    ListNode q = head;
    for(int i = 0; i < k-1; i++){
      if(q == null){
        return null;
      }
      q = q.next;
    }
    if(q == null){
      return null;
    }
    while(q.next != null){
      p = p.next;
      q = q.next;
    }
    return p;
  }

Idea 3:

Reverse the linked list, then the original problem becomes finding the k-th node with a positive number.

However, this changes the original linked list, and is not more efficient than idea 2

Reversal of linked list: refer to "Java Language Implementation of Reverse Linked List Code Example"

Summarize

The above is the detailed content of Java implements sample code sharing for outputting the k-th node from the bottom of a linked list. For more information, please follow other related articles on the PHP Chinese website!