Häufig verwendete Operationen für verknüpfte Listen – ausführliche Erläuterung der Umkehrung

Häufig verwendete Operationen für verknüpfte Listen – Umkehrung

Lassen Sie uns zunächst eine Knotenklasse für eine einfach verknüpfte Liste definieren

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

Implementieren einfach verknüpfte Liste Es gibt zwei Umkehrmethoden

1. Verwenden Sie die Rekursion und kehren Sie von hinten nach vorne um. Beginnen Sie am Kopfknoten, suchen Sie rückwärts, bis Sie den Endknoten finden, und beginnen Sie dann mit der Rückwärtsbewegung. ​

 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. Verwenden Sie die Quer- und Rückwärtsbewegung von vorne nach hinten. Speichern Sie zuerst den nächsten Knoten, verweisen Sie dann den aktuellen Knoten auf den vorherigen Knoten und verschieben Sie den Knoten dann nach unten, um den Zyklus für die nächste Umkehrung fortzusetzen.

 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     
 }

Sobald ich mit der Online-Programmierung fertig war, habe ich sie aufgezeichnet, damit ich sie in Zukunft leichter nachschlagen kann.

Das obige ist der detaillierte Inhalt vonHäufig verwendete Operationen für verknüpfte Listen – ausführliche Erläuterung der Umkehrung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!