上周出了進(jìn)行鏈表學(xué)習(xí)之外个绍，也進(jìn)行了整體時(shí)間的大致盤點(diǎn)勒葱，看了下時(shí)間≌厦常基本上的算法類型错森，在國慶之前都能刷一遍。
這周也是進(jìn)行的鏈表的算法練習(xí)篮洁，主要做了六道題
對以上的題目花了大概三個(gè)小時(shí)左右的時(shí)間寫完涩维，當(dāng)然期間看了題解，為了加深對題目的理解袁波，今天又對題目進(jìn)行復(fù)盤瓦阐，重新寫了一遍題目，花了大概兩個(gè)時(shí)間∨衽疲現(xiàn)在對題目有了一定的把握睡蟋，但是還是有誤差，得使用下周的時(shí)間再進(jìn)行復(fù)習(xí)了枷颊。
下面復(fù)盤題目：
第一題：刪除排序鏈表中的重復(fù)元素
package main
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil {
return nil
}
var pre = head
var cur = head.Next
for pre!= nil&&cur!=nil{
if pre.Val == cur.Val{
for ;cur!=nil&&cur.Val==pre.Val;cur=cur.Next{
}
pre.Next = cur
continue
}
pre = pre.Next
cur= cur.Next
}
return head
}
刪除鏈表中的重復(fù)節(jié)點(diǎn)戳杀，這題看著是簡單，但是在重寫的過程中夭苗，還是出現(xiàn)了卡殼信卡。題目的思路是使用雙指針，前后兩個(gè)指針题造，判斷值是否相等傍菇，值相等后指針繼續(xù)往后遍歷；值不相等前后兩個(gè)指針同時(shí)向后移動界赔《埃看著上面的指針移動是不是有點(diǎn)東西牵触。
第二題：刪除排序鏈表中的重復(fù)元素 II
這題和上面那題的區(qū)別在于只能保留原始節(jié)點(diǎn)中沒有重復(fù)的節(jié)點(diǎn)。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
// 輸入: 1->2->3->3->4->4->5
// 輸出: 1->2->5
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil{
return nil
}
var (
du = new(ListNode)
ret = du
cur = head.Next
pre = head
)
// [1,2,3,3,4,4,5]
du.Next = head
for cur != nil&&pre!=nil{
if pre.Val == cur.Val{
for ;cur!=nil&&cur.Val==pre.Val;cur=cur.Next{
}
ret.Next = cur
pre = cur
if cur != nil{
cur = cur.Next
}
continue
}
pre = pre.Next
cur = cur.Next
ret = ret.Next
}
return du.Next
}
思路：方法和之前的方法大致相同咐低，有點(diǎn)區(qū)別就是需要刪除全部重復(fù)的節(jié)點(diǎn)揽思，而不只是保留一個(gè)節(jié)點(diǎn)，為了滿足這點(diǎn)渊鞋，我們需要一個(gè)亞節(jié)點(diǎn)绰更。在鏈表中遍歷的時(shí)候，還是使用雙指針锡宋；如果出現(xiàn)了相同的節(jié)點(diǎn)儡湾，則后指針向后遍歷，直到出現(xiàn)不相同的節(jié)點(diǎn)，這時(shí)候?qū)喒?jié)點(diǎn)的Next進(jìn)行賦值，修改前后兩個(gè)指針毙籽；如果沒有出現(xiàn)相同的節(jié)點(diǎn)，則三個(gè)指針同時(shí)向后移動尝丐。這是三指針的算法。
第三題：反轉(zhuǎn)鏈表
這道是簡單的題目衡奥，代碼很簡單爹袁，題目也很容易理解，但是還真有需要注意的點(diǎn)矮固。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
if head == nil{
return nil
}
var (
pre *ListNode
cur = head
)
for cur!=nil{
var t = cur.Next
cur.Next = pre
pre = cur
cur = t
}
return pre
}
思路：使用雙指針失息，這里的前指針首先是空的（最后返回的也是前指針），后指針則首先指向頭結(jié)點(diǎn)档址。
第四題：反轉(zhuǎn)鏈表 II
這道題的題意倒是不難理解盹兢，就是旋轉(zhuǎn)鏈表中指定位置，從m到n的位置守伸。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
// 輸入: 1->2->3->4->5->NULL, m = 2, n = 4
// 輸出: 1->4->3->2->5->NULL
func reverseBetween(head *ListNode, m int, n int) *ListNode {
if head == nil{
return head
}
var index = m
var cur = head
var bHead *ListNode
for index!=1{
bHead = cur
cur = cur.Next
index--
}
var len = n-m
var startNode = cur
var pre = cur
var tailNode = cur
cur = cur.Next
for len!=0{
tailNode = cur
var t = cur.Next
cur.Next = pre
pre = cur
cur = t
len--
}
// 鏈接鏈表
if bHead !=nil{
bHead.Next = tailNode
}else{
head = tailNode
}
startNode.Next = cur
return head
}
思路：題目中因?yàn)閷和n的訪問進(jìn)行了顯示判斷绎秒，所以不必?fù)?dān)心m，n造成的越界尼摹。我們知道鏈表中的一部分進(jìn)行旋轉(zhuǎn)的時(shí)候有四個(gè)部分需要記錄见芹，分別是旋轉(zhuǎn)開始的上界，下屆蠢涝；旋轉(zhuǎn)結(jié)束的上界和下界玄呛。這在題目中分別是bHead，statrtNode惠赫，tailNode和cur這四個(gè)指針。對在書寫的時(shí)候總覺得思路不清晰故黑，現(xiàn)在這么一看倒是好點(diǎn)了儿咱。
分隔鏈表
這道題是使在小于x的值在大于等于x值的左邊庭砍，這道題，我的做法是首先遍歷鏈表混埠，然后把鏈表按照x分成小于x和大于x的兩部分怠缸，之后拼接兩個(gè)鏈表。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
// head = 1->4->3->2->5->2, x = 3
func partition(head *ListNode, x int) *ListNode {
if head == nil{
return head
}
var (
beforeHead = new(ListNode)
before = beforeHead
afterHead = new(ListNode)
after = afterHead
)
var cur = head
for cur!=nil{
if cur.Val < x{
before.Next = cur
before = before.Next
}else{
after.Next = cur
after = after.Next
}
cur = cur.Next
}
after.Next = nil
before.Next = afterHead.Next
return beforeHead.Next
}
第六題 重排鏈表
這道題我使用的方法還是鏈表拆分钳宪，首先遍歷鏈表揭北，獲取鏈表的長度，然后通過長度吏颖，把鏈表分成前后兩個(gè)部分搔体。對后一部分進(jìn)行倒置，然后進(jìn)行隔一的拼接半醉。
package main
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reorderList(head *ListNode) {
if head == nil{
return
}
listLen := GetListLen(head)
// 將鏈表變成兩段
var len = 0
var cur = head
for len!=listLen/2{
cur = cur.Next
len++
}
var firList = head
var secList = cur.Next
cur.Next = nil
// 重排第二個(gè)鏈表
secList = rankList(secList)
// 合并兩個(gè)鏈表
for firList != nil&&secList!=nil{
var fir = firList.Next
var sec = secList.Next
firList.Next = secList
secList.Next = fir
firList = fir
secList = sec
}
return
}
func GetListLen(head*ListNode)int{
var ret int
for head!=nil{
ret ++
head = head.Next
}
return ret
}
func rankList(head *ListNode)*ListNode{
if head == nil{
return head
}
var cur = head
var pre *ListNode
for cur!=nil{
var t = cur.Next
cur.Next = pre
pre = cur
cur = t
}
return pre
}
總結(jié)：
確實(shí)疚俱，在總結(jié)之后，發(fā)現(xiàn)對題目的理解更加深刻了缩多，到這里呆奕，鏈表的復(fù)習(xí)就告一段落了。接下來按照計(jì)劃是二叉樹了衬吆。
