[代码随想录]Day03-链表part01

题目：203. 移除链表元素

思路：

做链表首先最好有个虚拟头指针，这样做删除添加操作的时候可以统一操作否则还得特判。

那删除元素的过程，从虚拟头指针开始要做以下几步：

1. 如果当前p的next不为空，那么就可以进行判断
2. 如果p的next的值是val(↑p的next不为空↑)，那么就把p的next修改为p的下一项(p.next)的next，具体可以参考上图
3. 如果p的next的值不是val，那p = p.next继续向后遍历

因为我要维护的是p以及p的下一项p.next，所以当删除后p.next已经变成了先前的p.next.next所以p本身不需要移动；没有删除的话p需要移动。

代码：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    res := new(ListNode) // 创建一个*ListNode
    res.Next = head // 作为虚拟头指针
    p := res
    for p.Next != nil{ // 下一项不为空继续
        if p.Next.Val == val { // 如果下一项要删除
            p.Next = p.Next.Next // 把这一下的next改为下一项(p.next)的next
        } else {
            p = p.Next // 下一步
        }
    }
    return res.Next // res是虚拟头，res.Next才是结果
}

题目：707. 设计链表

思路：

究极整合题，核心内容就是如何使用这个虚拟头节点，值得推敲的一道题(毕竟把很多内容全用了)。

代码：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
type MyLinkedList struct {
    head *ListNode
    size int // 记录长度
}

func Constructor() MyLinkedList {
    return MyLinkedList{&ListNode{},0}
}


func (this *MyLinkedList) Get(index int) int {
    if index <0 || index >= this.size {
        return -1
    }
    cur := this.head // 虚拟头
    for i := 0; i <= index; i++ { 
        cur = cur.Next
    }
    return cur.Val
}


func (this *MyLinkedList) AddAtHead(val int)  {
    this.AddAtIndex(0, val) // 直接使用现成的插入
}


func (this *MyLinkedList) AddAtTail(val int)  {
    this.AddAtIndex(this.size, val) // 直接使用现成的插入
}


func (this *MyLinkedList) AddAtIndex(index int, val int)  {
    if index > this.size {
        return
    }
    if index < 0 {
        index = 0
    }
    this.size++
    cur := this.head
    for i:=0; i < index; i++ {
        cur = cur.Next
    }
    tmp := &ListNode{val,cur.Next}
    cur.Next = tmp
}


func (this *MyLinkedList) DeleteAtIndex(index int)  {
    if index < 0 || index >= this.size {
        return
    }
    this.size--
    cur := this.head
        for i:=0; i < index; i++ {
        cur = cur.Next
    }
    cur.Next = cur.Next.Next
}


/**
 * Your MyLinkedList object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Get(index);
 * obj.AddAtHead(val);
 * obj.AddAtTail(val);
 * obj.AddAtIndex(index,val);
 * obj.DeleteAtIndex(index);
 */

题目：206. 反转链表

思路：

说是双指针其实有三个只是由其中一个能直接得到。

三个指针l、r、t分别代表前一个元素，当前元素，以及下一个元素，那么翻转的步骤如下：

1. 让当前元素指向前一个元素r.Next = l
2. 把上一个元素更新为当前元素l = r
3. 把当前元素更新为下一个元素r = t

需要注意的几个问题：

1. 要把第一个元素的next改为nil
2. 结束时r == nil，因此我们返回的是上一个元素l而不是当前元素r

代码：

双指针

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var l *ListNode // 左初始nil
    r := head // 中
    for r != nil {
        t := r.Next // 右
        r.Next = l
        l = r
        r = t
    }
    return l
}