역방향 연결 목록을 구현하는 Java 코드 예제

이 글은 주로 Java 언어로 역방향 연결 목록을 구현하는 코드 예제를 소개합니다. 편집자는 그것이 필요하다고 생각하는 친구들을 위해 여기에 공유합니다.

문제 설명

연결 리스트의 헤드 노드를 입력하고, 연결 리스트를 반전시켜 역연결 리스트의 헤드 노드를 출력하는 함수를 정의하세요. 연결된 목록 노드는 다음과 같습니다.

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

아이디어 1:

연결된 목록을 되돌리려면 노드 i의 경우 이전 노드 옆을 가리켜야 하므로 이전 노드를 저장해야 합니다. 동시에, i의 다음을 재할당했다면 i의 후임자를 찾을 수 없기 때문에 재할당하기 전에 i의 후임자를 저장해야 합니다.

코드:

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

아이디어 2:

재귀 아이디어를 사용하세요. (아직 생각해 본 적이 없습니다. 왜냐하면 재귀를 사용한다면 매번 다음과 같아야 하기 때문입니다. the linked list<-재귀로 반환된 연결리스트의 tail 포인터인데, 이 경우 반전된 head 포인터를 얻을 수 없다.) 나중에 생각해 보자.

요약

위 내용은 역방향 연결 목록을 구현하는 Java 코드 예제의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!