演算法 - 鏈表操作題目套路 前面這一篇文章主要講鏈表操作時候的實操解決方式，本文從本質講解鏈表操作的元資訊，學完后，再也不怕鏈表操作題目了，
1.鏈表的基本操作
鏈表的基本操作無外乎插入，洗掉，遍歷
插入的化，要考慮到前驅節點和后繼節點，記住下面的偽代碼
nex = 當前節點.next
當前節點.next = 插入的指標
插入指標.next = tmp
對于洗掉，是否會覺得需要備份一下next的指標，答案是不用，執行陳述句是先取右邊的值存起來然后賦值給左邊的，所以直接下面一句話即可
cur.next = cur.next.next
對于遍歷，實際上是又迭代和遞回的，另外又有前序和后序
cur = head
while cur != null {
print(cur)
cur = cur.next
}
//前序
dfs(cur) {
if cur == null return
print(cur.val)
return dfs(cur.next)
}
2.鏈表的考點
鏈表的考點就只有對指標的修改和對指標的拼接，其中都需要對指標的前驅節點和后繼節點進行保留，如果頭節點不能首次確定，或者可能會改變，那么又需要一個虛擬頭節點，鏈表的考點無外乎就這些，
下面我們來看兩個題
洗掉鏈表中的重復元素
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
public ListNode deleteDuplicates(ListNode head) {
//遞回版
if (head == null || head.next == null)
return head;
if (head.val == head.next.val) {
while (head.next != null && head.next.val == head.val)
head = head.next;
head = deleteDuplicates(head.next);
} else {
head.next = deleteDuplicates(head.next);
}
return head;
}
判斷是否為回文鏈表
https://leetcode-cn.com/problems/palindrome-linked-list/
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null)return true;
temp = head;
return dfs(head);
}
public boolean dfs(ListNode head){
if(head == null)return true;
boolean res = dfs(head.next) && temp.val == head.val;
temp = temp.next;
return res;
}
總結，鏈表的題目，掌握號指標的操作，就會簡單點了，對于遞回寫法也會簡化很多代碼
吳邪，小三爺，混跡于后臺，大資料，人工智能領域的小菜鳥，
更多請關注
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/264406.html
標籤：其他
上一篇：「SOL」謝特(LOJ)
下一篇：軟體測驗實體（二）