연결된 목록에서 일반적으로 사용되는 작업 - 반전에 대한 자세한 설명

연결된 목록에서 일반적으로 사용되는 작업 - 역전

먼저 단일 연결 목록에 대한 노드 클래스를 정의하겠습니다

public class ListNode {2         
int val;3         ListNode next = null;// 指向的下个节点4 5         
ListNode(int val) {6             this.val = val;7         }8     
}

단일 연결 목록을 역전시키는 방법에는 두 가지가 있습니다

1. 뒤로 앞으로. 헤드 노드에서 시작하여 테일 노드를 찾을 때까지 뒤로 검색한 다음 역방향을 시작합니다. ​

 1     public ListNode reverseList(ListNode head) { 2         
 if (head == null || head.next == null) 3             return head; 4  5         
 ListNode prev = reverseList(head.next);// 递归调用,先反转下个节点 6  7         
 head.next.next = head;// 将当前结点的指针域指向前一结点 8         
 head.next = null;// 前一结点的指针域令为null; 9         
 return prev;// 反转后新链表的头结点10     
 }

2. 앞에서 뒤로 순회 및 역순을 사용합니다. 먼저 다음 노드를 저장한 다음 현재 노드를 이전 노드로 지정한 다음 노드를 아래로 이동하여 다음 반전을 위한 주기를 계속합니다.

 1     public ListNode reverseList(ListNode head) { 2         if (head == null) { 3             
 return null; 4         } 5         ListNode pre = null; 6         
 ListNode next = null; 7         while (head != null) { 8             
 // 保存下个节点,防止丢失 9             next = head.next;10             
 // 将他的下个节点指向前个节点11             head.next = pre;12 13             
 // head指向pre后，就继续依次反转下个节点14             
 // 让pre，head依次向后移动一个节点，继续下一次的反转15             
 pre = head;16             head = next;17         }18         
 return pre;19     
 }

방금 온라인 프로그래밍을 마치고 나중에 참고하기 쉽게 녹화했습니다.

위 내용은 연결된 목록에서 일반적으로 사용되는 작업 - 반전에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!