B站圖靈星球的視頻總結的檔案，傳送門
基本都是雙指標法，一個移動快，一個移動慢，
定義
public class ListNode {
int val;
ListNode next;
ListNode(int x){ val = x; }
}
1. Linked List找中間節點
兩個指標同向而行，一個每次前進2個節點，另一個每次前進1個節點，當快指標到最后，慢指標就停留在中點，
public ListNode LinkedListMiddleNode (ListNode head){
ListNode i = head;
ListNode j = head;
while(j != null && j.next != null){
i = i.next;
j = j.next.next;
}
return i;
}
2. Linked List找倒數第K個節點(LeetCode面試題02.02）
先使兩個指標相隔K個位置，然后使每次以相同的速度向前移動，當快指標出界時候，慢指標就停留在倒數第K個位置
public ListNode LinkedListLastKthNode(ListNode head,int k){
ListNode i = head;
ListNode j = head;
for(int a = 0; a < k; a++){
j = j.next; //使i和j相隔K個節點
}
while(j != null){
i = i.next;
j = j.next;
}
return i;
}
3. 反轉鏈表(LeetCode面試題24）
可以使用遞回或者迭代，
1->2->3->4->5反轉后變為1<-2<-3<-4<-5
public ListNode reverse(ListNode head){
if(head == null || head.next == null){
return head;
ListNode reversed_head = reverse(head.next);
head.next.next = head;
head.next = null;
return reversed_head;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/43514.html
標籤：其他