이 글은 주로 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; }
연결된 목록을 뒤집으면 원래 문제는 양의 k번째 노드를 찾는 것입니다.
그러나 이는 원래 연결 목록을 변경하며 아이디어 2보다 효율적이지 않습니다. 2
연결 목록 반전: "역방향 연결 목록 코드 예제의 Java 언어 구현"을 참조하세요.
요약
위 내용은 Java는 연결 목록의 맨 아래에서 k번째 노드를 출력하기 위한 샘플 코드 공유를 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!