前言
之前小六六一直覺得自己的算法比較菜,算是一個短闆吧,以前刷題也還真是三天打魚,兩台曬網,刷幾天,然後就慢慢的不堅持了,是以這次,借助平台的活動,打算慢慢的開始開刷,并且自己還會給刷的題總結下,談談自己的一些思考,和自己的思路等等,希望對小夥伴能有所幫助吧,也可以借此機會把自己短闆補一補,希望自己能堅持下去呀
連結清單
- 六六力扣刷題連結清單之移除連結清單元素
- 六六力扣刷題連結清單之反轉連結清單
- 六六力扣刷題連結清單之兩兩交換連結清單中的節點
- 六六力扣刷題連結清單之合并兩個有序連結清單
連結清單的理論基礎
連結清單的種類主要為:單連結清單,雙連結清單,循環連結清單
連結清單的存儲方式:連結清單的節點在記憶體中是分散存儲的,通過指針連在一起。
連結清單是如何進行增删改查的。
數組和連結清單在不同場景下的性能分析。
可以說把連結清單基礎的知識都概括了,但又不像教科書那樣的繁瑣。
虛拟頭結點
連結清單的一大問題就是操作目前節點必須要找前一個節點才能操作。這就造成了,頭結點的尴尬,因為頭結點沒有前一個節點了。
每次對應頭結點的情況都要單獨處理,是以使用虛拟頭結點的技巧,就可以解決這個問題。
題目
給定一個已排序的連結清單的頭
head
, 删除原始連結清單中所有重複數字的節點,隻留下不同的數字 。傳回 已排序的連結清單 。
輸入: head = [1,2,3,3,4,4,5]
輸出: [1,2,5]
題解
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (null == head || null == head.next) {
return head;
}
ListNode dumy = new ListNode(0);
dumy.next = head;
ListNode current = dumy;
while (current.next != null && current.next.next != null) {
if (current.next.val == current.next.next.val) {
int vaal = current.next.val;
while (current.next!=null&&vaal==current.next.val){
current.next=current.next.next;
}
}else {
current=current.next;
}
}
return dumy.next;
思路與算法
由于給定的連結清單是排好序的,是以重複的元素在連結清單中出現的位置是連續的,是以我們隻需要對連結清單進行一次周遊,就可以删除重複的元素。由于連結清單的頭節點可能會被删除,是以我們需要額外使用一個啞節點(dummy node)指向連結清單的頭節點。
具體地,我們從指針 cur 指向連結清單的啞節點,随後開始對連結清單進行周遊。如果目前cur.next 與 cur.next.next 對應的元素相同,那麼我們就需要将 cur.next 以及所有後面擁有相同元素值的連結清單節點全部删除。我們記下這個元素值 xx,随後不斷将 cur.next 從連結清單中移除,直到 cur.next 為空節點或者其元素值不等于 xx 為止。此時,我們将連結清單中所有元素值為 xx 的節點全部删除。