上周出了进行链表学习之外，也进行了整体时间的大致盘点，看了下时间。基本上的算法类型，在国庆之前都能刷一遍。
这周也是进行的链表的算法练习，主要做了六道题
对以上的题目花了大概三个小时左右的时间写完，当然期间看了题解，为了加深对题目的理解，今天又对题目进行复盘，重新写了一遍题目，花了大概两个时间。现在对题目有了一定的把握，但是还是有误差，得使用下周的时间再进行复习了。
下面复盘题目：
第一题：删除排序链表中的重复元素
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
}
删除链表中的重复节点，这题看着是简单，但是在重写的过程中，还是出现了卡壳。题目的思路是使用双指针，前后两个指针，判断值是否相等，值相等后指针继续往后遍历；值不相等前后两个指针同时向后移动。看着上面的指针移动是不是有点东西。
第二题：删除排序链表中的重复元素 II
这题和上面那题的区别在于只能保留原始节点中没有重复的节点。
/**
* 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
}
思路：方法和之前的方法大致相同，有点区别就是需要删除全部重复的节点，而不只是保留一个节点，为了满足这点，我们需要一个亚节点。在链表中遍历的时候，还是使用双指针；如果出现了相同的节点，则后指针向后遍历，直到出现不相同的节点，这时候对亚节点的Next进行赋值，修改前后两个指针；如果没有出现相同的节点，则三个指针同时向后移动。这是三指针的算法。
第三题：反转链表
这道是简单的题目，代码很简单，题目也很容易理解，但是还真有需要注意的点。
/**
* 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
}
思路：使用双指针，这里的前指针首先是空的（最后返回的也是前指针），后指针则首先指向头结点。
第四题：反转链表 II
这道题的题意倒是不难理解，就是旋转链表中指定位置，从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
}
思路：题目中因为对m和n的访问进行了显示判断，所以不必担心m，n造成的越界。我们知道链表中的一部分进行旋转的时候有四个部分需要记录，分别是旋转开始的上界，下届；旋转结束的上界和下界。这在题目中分别是bHead，statrtNode，tailNode和cur这四个指针。对在书写的时候总觉得思路不清晰，现在这么一看倒是好点了。
分隔链表
这道题是使在小于x的值在大于等于x值的左边，这道题，我的做法是首先遍历链表，然后把链表按照x分成小于x和大于x的两部分，之后拼接两个链表。
/**
* 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
}
第六题 重排链表
这道题我使用的方法还是链表拆分，首先遍历链表，获取链表的长度，然后通过长度，把链表分成前后两个部分。对后一部分进行倒置，然后进行隔一的拼接。
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
// 重排第二个链表
secList = rankList(secList)
// 合并两个链表
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
}
总结：
确实，在总结之后，发现对题目的理解更加深刻了，到这里，链表的复习就告一段落了。接下来按照计划是二叉树了。
