系列:鏈表專練
語言:java & go
題目來源:Leetcode
常考點: 單鏈表 & 雙鏈表 &雙指針
給你一個鏈表的頭節(jié)點 head 和一個整數 val ,請你刪除鏈表中所有滿足 Node.val == val 的節(jié)點,并返回 新的頭節(jié)點 。
分析:如果需要刪除第三個節(jié)點,那我們應該知道前一個節(jié)點才能完成相關操作。那么如果只有一個節(jié)點head時,如何進行操作呢,那就要進行相關判斷,所以我們可以建一個虛擬頭節(jié)點來使對每個符合條件的節(jié)點進行相同的刪除操作,就是通過前一個節(jié)點來進行刪除操作
java參考代碼:
class Solution {public ListNode removeElements(ListNode head, int val) {if(head == null){return head;
}
ListNode dummy = new ListNode(-1,head);
ListNode pre = dummy;
ListNode cur = head;
while(cur!= null){if(cur.val == val){pre.next = cur.next;
}else{pre = cur;
}
cur = cur.next;
}
//這里為什么要返回dummy.next 而不是head呢?
//因為新的頭節(jié)點使dummy.next,而不是原來的head了
return dummy.next;
}
}
go參考代碼:
func removeElements(head *ListNode, val int) *ListNode {dummy := &ListNode{}
dummy.Next = head
cur := dummy
for cur != nil && cur.Next != nil {if cur.Next.Val == val { cur.Next = cur.Next.Next
} else { cur = cur.Next
}
}
return dummy.Next
}
設計鏈表的實現。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節(jié)點應該具有兩個屬性:val 和 next。val 是當前節(jié)點的值,next 是指向下一個節(jié)點的指針/引用。如果要使用雙向鏈表,則還需要一個屬性 prev 以指示鏈表中的上一個節(jié)點。假設鏈表中的所有節(jié)點都是 0-index 的。
在鏈表類中實現這些功能:
get(index):獲取鏈表中第 index 個節(jié)點的值。如果索引無效,則返回-1。
addAtHead(val):在鏈表的第一個元素之前添加一個值為 val 的節(jié)點。插入后,新節(jié)點將成為鏈表的第一個節(jié)點。
addAtTail(val):將值為 val 的節(jié)點追加到鏈表的最后一個元素。
addAtIndex(index,val):在鏈表中的第 index 個節(jié)點之前添加值為 val 的節(jié)點。如果 index 等于鏈表的長度,則該節(jié)點將附加到鏈表的末尾。如果 index 大于鏈表長度,則不會插入節(jié)點。如果index小于0,則在頭部插入節(jié)點。
deleteAtIndex(index):如果索引 index 有效,則刪除鏈表中的第 index 個節(jié)點。
這道題非常適合用來練習鏈表相關操作,可以多加練習熟悉鏈表的操作,這里使用的依然是添加虛擬頭節(jié)點的前提,不懂的可以跟著先敲,多敲幾遍就理解其中的含義了,我至少跟著敲了十遍,才漸漸明白鏈表的相關操作以及含義,好事多磨!
java解法:分為單鏈表實現和雙鏈表實現
//單鏈表解法
class ListNode{int val;
ListNode next;
ListNode(){};
ListNode(int val){ this.val = val;
}
}
class MyLinkedList {int size;
ListNode head;
ListNode dummy;
public MyLinkedList() {size = 0;
head = new ListNode(0);
dummy = new ListNode(-1);
head = dummy.next;
}
public int get(int index) {if(index< 0 || index >=size){return -1;
}
ListNode cur = dummy;
for(int i =0;icur = cur.next;
}
return cur.next.val;
}
public void addAtHead(int val) {addAtIndex(0,val);
}
public void addAtTail(int val) {addAtIndex(size,val);
}
public void addAtIndex(int index, int val) {if(index >size){return;
}
if(index< 0){index = 0;
}
size++;
ListNode perd = dummy;
for(int i =0;iperd = perd.next;
}
ListNode toAdd = new ListNode(val);
toAdd.next = perd.next;
perd.next = toAdd;
}
public void deleteAtIndex(int index) {if(index<0 || index >= size){return;
}
size--;
ListNode perd = dummy;
for(int i =0;iperd = perd.next;
}
perd.next = perd.next.next;
}
}
//雙鏈表寫法
//雙鏈表
class ListNode{int val;
ListNode next,prev;
ListNode() {};
ListNode(int val){this.val = val;
}
}
class MyLinkedList {//記錄鏈表中元素的數量
int size;
//記錄鏈表的虛擬頭結點和尾結點
ListNode head,tail;
public MyLinkedList() {//初始化操作
this.size = 0;
this.head = new ListNode(0);
this.tail = new ListNode(0);
//這一步非常關鍵,否則在加入頭結點的操作中會出現null.next的錯誤!!!
head.next=tail;
tail.prev=head;
}
public int get(int index) {//判斷index是否有效
if(index<0 || index>=size){return -1;
}
ListNode cur = this.head;
//判斷是哪一邊遍歷時間更短
if(index >= size / 2){//tail開始
cur = tail;
for(int i=0; i< size-index; i++){cur = cur.prev;
}
}else{for(int i=0; i<= index; i++){cur = cur.next;
}
}
return cur.val;
}
public void addAtHead(int val) {//等價于在第0個元素前添加
addAtIndex(0,val);
}
public void addAtTail(int val) {//等價于在最后一個元素(null)前添加
addAtIndex(size,val);
}
public void addAtIndex(int index, int val) {//index大于鏈表長度
if(index>size){return;
}
//index小于0
if(index<0){index = 0;
}
size++;
//找到前驅
ListNode pre = this.head;
for(int i=0; ipre = pre.next;
}
//新建結點
ListNode newNode = new ListNode(val);
newNode.next = pre.next;
pre.next.prev = newNode;
newNode.prev = pre;
pre.next = newNode;
}
public void deleteAtIndex(int index) {//判斷索引是否有效
if(index<0 || index>=size){return;
}
//刪除操作
size--;
ListNode pre = this.head;
for(int i=0; ipre = pre.next;
}
pre.next.next.prev = pre;
pre.next = pre.next.next;
}
}
go參考代碼: 分為單鏈表和雙鏈表實現
//單鏈表實現
// 節(jié)點結構體
type Node struct {Val int
Next *Node
}
// MylinkedList是一個對象,需要去實現LinkedList接口的所有方法
type MyLinkedList struct {DummyHead *Node //虛擬頭節(jié)點
Size int //鏈表長度
}
//創(chuàng)建一個鏈表
func Constructor() MyLinkedList {//成功
// 創(chuàng)建一個虛擬頭節(jié)點,非真正的頭節(jié)點(真正的頭節(jié)點是數組第一個節(jié)點)
dummyHead := &Node{Val : -1,
Next : nil,
}
return MyLinkedList{DummyHead: dummyHead,Size: 0}
}
// 獲取index位置的元素Val
// 獲取到第index個節(jié)點數值,如果index是非法數值直接返回-1, 注意index是從0開始的,第0個節(jié)點就是頭結點
func (this *MyLinkedList) Get(index int) int {// 判斷index是否非法
if (index< 0) || (index >(this.Size - 1)) {return -1
}
// 查找
var cur *Node = this.DummyHead// dummy節(jié)點的index = -1
for i := 0;i< index;i++ {//找到index為 index的節(jié)點
cur = cur.Next //0,1,2,3,4....index
}
return cur.Next.Val
}
// 在頭節(jié)點前面再次添加一個節(jié)點
func (this *MyLinkedList) AddAtHead(val int) {//成功
// 在dummy節(jié)點后面直接添加一個節(jié)點
var newNode *Node = &Node{Val:val, Next:nil,} //所有變量都要顯示的初始化
newNode.Next = this.DummyHead.Next
this.DummyHead.Next = newNode
this.Size++
}
// 在尾結點添加節(jié)點
func (this *MyLinkedList) AddAtTail(val int) {var newNode *Node = &Node{val, nil}
cur := this.DummyHead
for cur.Next != nil {//找到末尾節(jié)點
cur = cur.Next
}
cur.Next = newNode //新元素添加到末尾節(jié)點后面
this.Size++
}
// 在index節(jié)點前面添加一個節(jié)點
func (this *MyLinkedList) AddAtIndex(index int, val int) {if index >this.Size {return
}else if index == this.Size {//直接添加到末尾
this.AddAtTail(val)
return
}else if index< 0 {index = 0
}
var newNode *Node = &Node{val, nil}
cur := this.DummyHead
for i:=0; i//找到index為 index-1的節(jié)點,如果index=0,則不會進入循環(huán),直接插入到dummy后面
cur = cur.Next
}
newNode.Next = cur.Next
cur.Next = newNode
this.Size++
}
// 刪除index節(jié)點
func (this *MyLinkedList) DeleteAtIndex(index int) {// 判斷是否有效
if index >this.Size-1 || index< 0 {return
}
cur := this.DummyHead
for i := 0; i< index; i++ {cur = cur.Next
}
cur.Next = cur.Next.Next
this.Size--
}
// func main(){// obj := Constructor()
// obj.AddAtHead(1)
// obj.AddAtTail(2)
// obj.AddAtIndex(0,0)
// obj.DeleteAtIndex(0)
// fmt.Println(obj.Get(0),obj.Get(1),obj.Get(2))
// }
//雙鏈表寫法
//雙鏈表解法
// 節(jié)點結構體
type Node struct {Val int
Next *Node
Pre *Node
}
// 鏈表對象
type MyLinkedList struct {DummyHead *Node
DummyTail *Node
Size int
}
// 創(chuàng)建一個有虛擬首位節(jié)點的鏈表
func Constructor() MyLinkedList {dummyHead := &Node{-1, nil, nil}
dummyTail := &Node{-1, nil, dummyHead}
dummyHead.Next = dummyTail
return MyLinkedList{dummyHead, dummyTail, 0}
}
// 獲取index節(jié)點
func (this *MyLinkedList) Get(index int) int {if index >= this.Size || index< 0 {return -1
} else {p := this.DummyHead
for i := 0; i< index; i++ { p = p.Next
}
return p.Next.Val
}
}
// 在頭結點前面添加一個節(jié)點稱為新的頭節(jié)點
func (this *MyLinkedList) AddAtHead(val int) {var newNode *Node = &Node{val, nil, nil}
//后插法添加節(jié)點
newNode.Next = this.DummyHead.Next
newNode.Pre = this.DummyHead
this.DummyHead.Next.Pre = newNode
this.DummyHead.Next = newNode
this.Size++
}
// 在尾結點后面添加一個節(jié)點
func (this *MyLinkedList) AddAtTail(val int) {//在dummytail前面添加一個節(jié)點
var newNode *Node = &Node{val, nil, nil}
//前插法添加節(jié)點
newNode.Next = this.DummyTail
newNode.Pre = this.DummyTail.Pre
this.DummyTail.Pre.Next = newNode
this.DummyTail.Pre = newNode
this.Size++
}
// 在指定位置插入一個節(jié)點
func (this *MyLinkedList) AddAtIndex(index int, val int) {if index >this.Size {return
} else if index< 0 {this.AddAtHead(val)
} else {p := this.DummyHead
for i := 0; i< index; i++ { p = p.Next
}
var newNode *Node = &Node{val, p.Next, p}
p.Next.Pre = newNode
p.Next = newNode
this.Size++
}
}
// 刪除指定index的節(jié)點
func (this *MyLinkedList) DeleteAtIndex(index int) {if index >= this.Size || index< 0 {return
} else {p := this.DummyHead
for i := 0; i< index; i++ { p = p.Next
}
p.Next.Next.Pre = p
p.Next = p.Next.Next
this.Size--
}
}
給你單鏈表的頭節(jié)點 head ,請你反轉鏈表,并返回反轉后的鏈表。
思路:通過快慢指針,來改變鏈表的指向,將鏈表的指向反過來,如果本來指針指向是1->2->3,我們將鏈表指向改為1<-2<-3,通過移動兩個指針來實現,最后打印輸出指針即可
java參考代碼:雙指針和遞歸
//雙指針
class Solution {public ListNode reverseList(ListNode head) {ListNode pre=null ;
ListNode temp =null;
ListNode cur = head;
while(cur != null){temp = cur.next;
cur.next = pre;
pre = cur;
cur= temp;
}
return pre;
}
}
//遞歸
class Solution{public ListNode reverseList(ListNode head){return reverse(null,head);
}
private ListNode reverse(ListNode pre,ListNode cur){if(cur == null){return pre;
}
ListNode temp = null;
temp = cur.next; //先保存下一個節(jié)點
cur.next = pre; //反轉
//更新pre cur位置
return reverse(cur,temp);
}
}
go參考代碼: 雙指針和遞歸
//雙指針
func reverseList(head *ListNode) *ListNode {var pre *ListNode
cur := head
for cur != nil {next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
return pre
}
//遞歸
func reverseList(head *ListNode) *ListNode {return help(nil, head)
}
func help(pre, head *ListNode)*ListNode{if head == nil {return pre
}
next := head.Next
head.Next = pre
return help(head, next)
}
給你一個鏈表,兩兩交換其中相鄰的節(jié)點,并返回交換后鏈表的頭節(jié)點。你必須在不修改節(jié)點內部的值的情況下完成本題(即,只能進行節(jié)點交換)。
思路:有一點你需要明白,鏈表不同于其他類型,如果要交換兩個節(jié)點的位置,需要改變的是指針的指向,比如dummy(虛擬頭結點)->1->2->3->4,我們交換完后是dummy(虛擬頭結點)->2->1->4->3,怎樣實現:將頭結點的next指向2,而不是指向1,將2的next指向1,1的next指向4,4的next指向3,這樣的話就實現了交換兩個節(jié)點。
java實現:
class Solution {public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(-1,head);
ListNode cur = dummy;
ListNode temp;
ListNode firstNode;
ListNode secondNode;
while(cur.next != null && cur.next.next != null){temp = cur.next.next.next;
firstNode = cur.next;
secondNode = cur.next.next;
cur.next = secondNode;
secondNode.next = firstNode;
firstNode.next = temp;
cur = firstNode; //cur移動,準備下一輪交換
}
return dummy.next;
}
}
go實現:
func swapPairs(head *ListNode) *ListNode {dummy := &ListNode{Next: head,
}
pre := dummy
for head != nil && head.Next != nil{pre.Next = head.Next
next := head.Next.Next
head.Next.Next = head
head.Next = next
pre = head
head = next
}
return dummy.Next
}
給你一個鏈表,刪除鏈表的倒數第 n 個結點,并且返回鏈表的頭結點。
思路:雙指針思路,:通過將slow和fast兩個指針之間間隔為n,即fast比slow多走n步,然后根據判斷fast的下一個節(jié)點是否是空,然后此時slow指向的剛好是目標節(jié)點的前一個節(jié)點,所以可以完成刪除
//雙指針解法:通過將slow和fast兩個指針之間間隔為n,即fast比slow多走n步
//
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1,head);
ListNode fastNode = dummy;
ListNode slowNode = dummy;
for(int i =0;ifastNode = fastNode.next;
}
while(fastNode.next != null){fastNode = fastNode.next;
slowNode = slowNode.next;
}
slowNode.next = slowNode.next.next;
return dummy.next;
}
}
go語言版本同樣的道理:通過一快一慢指針,先將fast指針比slow指針快移動n步,然后再開始移動slow指針,類比上面java的思路 一樣的
func removeNthFromEnd(head *ListNode, n int) *ListNode {dummy := &ListNode{}
dummy.Next = head
cur := head
pre := dummy
i:=1
for cur!= nil{cur= cur.Next
if i>n{pre = pre.Next
}
i++
}
pre.Next = pre.Next.Next
return dummy.Next
}
給你兩個單鏈表的頭節(jié)點 headA 和 headB ,請你找出并返回兩個單鏈表相交的起始節(jié)點。如果兩個鏈表沒有交點,返回 null 。
思路:首先要想比較兩個鏈表的相同點,比較的不是開頭,長的鏈表需要向后移動兩個鏈表長度差,然后才能開始比較,這個是前提,所以我們同時也需要分別統(tǒng)計出鏈表a和鏈表b的長度;然后對齊后開始比較,有相同交點直接返回
java方法:
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA = headA;
ListNode curB = headB;
int lenA = 0,lenB = 0;
while(curA != null){//求鏈表A的長度
lenA++;
curA = curA.next;
}
while(curB != null){//求鏈表B的長度
lenB++;
curB = curB.next;
}
curA = headA;
curB = headB;
if(lenB>lenA){int tmplen = lenA;
lenA = lenB;
lenB = tmplen;
ListNode tmpNode =curA;
curA = curB;
curB = tmpNode;
}
//求長度差
int gap = lenA-lenB;
//讓curA和curB在同一起點上(末尾位置對齊)
while(gap-->0){curA = curA.next;
}
while(curA != null){if(curA == curB){return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}
go方法:
func getIntersectionNode(headA, headB *ListNode) *ListNode {curA := headA
curB := headB
lenA, lenB := 0, 0
// 求A,B的長度
for curA != nil {curA = curA.Next
lenA++
}
for curB != nil {curB = curB.Next
lenB++
}
var step int
var fast, slow *ListNode
// 請求長度差,并且讓更長的鏈表先走相差的長度
if lenA >lenB {step = lenA - lenB
fast, slow = headA, headB
} else {step = lenB - lenA
fast, slow = headB, headA
}
for i:=0; i< step; i++ {fast = fast.Next
}
// 遍歷兩個鏈表遇到相同則跳出遍歷
for fast != slow {fast = fast.Next
slow = slow.Next
}
return fast
}
給定一個鏈表的頭節(jié)點 head ,返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán),則返回 null。如果鏈表中有某個節(jié)點,可以通過連續(xù)跟蹤 next 指針再次到達,則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán),評測系統(tǒng)內部使用整數 pos 來表示鏈表尾連接到鏈表中的位置(索引從 0 開始)。如果 pos 是 -1,則在該鏈表中沒有環(huán)。注意:pos 不作為參數進行傳遞,僅僅是為了標識鏈表的實際情況。
不允許修改 鏈表。
思路:首先判斷是否有環(huán),通過雙指針進行判斷,一快一慢,fast快指針比slow慢指針每次多走一步,如果有環(huán)的話,快慢指針會相遇的,否則無環(huán);如果找到環(huán)的出口,因為每次fast快指針走的路程是慢指針走的路程的兩倍,所以根據數學公式。
假設從頭結點到環(huán)形入口節(jié)點 的節(jié)點數為x。 環(huán)形入口節(jié)點到 fast指針與slow指針相遇節(jié)點 節(jié)點數為y。 從相遇節(jié)點 再到環(huán)形入口節(jié)點節(jié)點數為 z。
那么相遇時: slow指針走過的節(jié)點數為: x + y, fast指針走過的節(jié)點數:x + y + n (y + z),n為fast指針在環(huán)內走了n圈才遇到slow指針, (y+z)為 一圈內節(jié)點的個數A。
因為fast指針是一步走兩個節(jié)點,slow指針一步走一個節(jié)點, 所以 fast指針走過的節(jié)點數 = slow指針走過的節(jié)點數 * 2:
(x + y) * 2 = x + y + n (y + z)
兩邊消掉一個(x+y): x + y = n (y + z)
因為要找環(huán)形的入口,那么要求的是x,因為x表示 頭結點到 環(huán)形入口節(jié)點的的距離。
所以要求x ,將x單獨放在左面:x = n (y + z) - y ,
再從n(y+z)中提出一個 (y+z)來,整理公式之后為如下公式:x = (n - 1) (y + z) + z 注意這里n一定是大于等于1的,因為 fast指針至少要多走一圈才能相遇slow指針。
先拿n為1的情況來舉例,意味著fast指針在環(huán)形里轉了一圈之后,就遇到了 slow指針了。
當 n為1的時候,公式就化解為 x = z
java解法:
public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){slow = slow.next;
fast = fast.next.next;
if(slow == fast){//有環(huán)
ListNode index1 = fast;
ListNode index2 = head;
while(index1 != index2){index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}
go解法:
func detectCycle(head *ListNode) *ListNode {slow, fast := head, head
for fast != nil && fast.Next != nil {slow = slow.Next
fast = fast.Next.Next
if slow == fast {for slow != head {slow = slow.Next
head = head.Next
}
return head
}
}
return nil
}
希望對您的算法學習能有所幫助,您的支持是我前進的大動力,感謝您的關注和認可!!!
你是否還在尋找穩(wěn)定的海外服務器提供商?創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源,準確流量調度確保服務器高可用性,企業(yè)級服務器適合批量采購,新人活動首月15元起,快前往官網查看詳情吧
網頁題目:Leetcode鏈表專題專練-萬字總結-創(chuàng)新互聯(lián)
瀏覽路徑:http://vcdvsql.cn/article14/dsddge.html
成都網站建設公司_創(chuàng)新互聯(lián),為您提供品牌網站設計、微信公眾號、網站改版、搜索引擎優(yōu)化、網站收錄、標簽優(yōu)化
聲明:本網站發(fā)布的內容(圖片、視頻和文字)以用戶投稿、用戶轉載內容為主,如果涉及侵權請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內容未經允許不得轉載,或轉載時需注明來源: 創(chuàng)新互聯(lián)