Java는 연결 목록의 맨 아래에서 k번째 노드를 출력하기 위한 샘플 코드 공유를 구현합니다.

이 글은 주로 Java 출력 링크 목록의 하단에서 k번째 노드의 관련 내용을 소개하며, 여기에는 세 가지 디자인 아이디어와 코드 예제가 포함되어 있습니다. 필요한 친구는 이에 대해 알아볼 수 있습니다.

문제 설명

연결리스트를 입력하고 연결리스트의 마지막 노드부터 k번째 노드를 출력합니다. (꼬리 노드가 마지막 노드입니다.) 노드 정의는 다음과 같습니다:

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

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

아이디어 1:

먼저 연결 리스트를 순회하고 길이를 계산합니다. 그런 다음 맨 아래에서 k번째 노드를 계산합니다. 는 양수 길이 - k + 1입니다. 마지막으로 원하는 노드를 찾기 위해 연결된 목록을 순회합니다.

시간 복잡도는 O(2n)이고 연결 목록을 두 번 순회해야 합니다.

코드는 다음과 같습니다.

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

아이디어 2:

연결된 목록을 한 번만 순회하여 얻을 수 있다고 기대하세요. 두 개의 포인터를 설정합니다. 하나는 첫 번째 노드를 가리키도록 초기화되고 두 번째 포인터는 k번째 노드를 가리키도록 설정됩니다. 그런 다음 두 포인터가 동기적으로 뒤로 이동합니다. 두 번째 포인터가 꼬리 노드를 가리킬 때 첫 번째 포인터는 아래쪽에서 k번째 노드를 가리킵니다

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

아이디어 3:

연결된 목록을 뒤집으면 원래 문제는 양의 k번째 노드를 찾는 것입니다.

그러나 이는 원래 연결 목록을 변경하며 아이디어 2보다 효율적이지 않습니다. 2

연결 목록 반전: "역방향 연결 목록 코드 예제의 Java 언어 구현"을 참조하세요.

요약

위 내용은 Java는 연결 목록의 맨 아래에서 k번째 노드를 출력하기 위한 샘플 코드 공유를 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!