文章：4. 翻转链表.url

链表

链表是一种通过指针串联在一起的线性结构，每个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）

链表的入口节点称为链表的头节点也就是head。

链表类型

单链表

上面定义的就是单链表

双链表

单链表中的指针域只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表既可以向前查询也可以向后查询。

循环链表

循环链表，链表首尾相连。

可以用来解决约瑟夫环问题。

链表的存储方式

数组是在内存中连续分布的，但是链表在内存中不是连续分布的。

链表通过指针域的指针链接在内存中的各个节点，所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表的定义

struct ListNode{
	int val; //节点上存储的元素
	ListNode *next; //指向下一个节点的指针
	ListNode(int x): val(x),next(NULL){} //节点的构造函数
}

通过自己定义构造函数初始化节点：

1	ListNode* head = new ListNode(5);

使用默认构造函数初始化节点：

1 2	ListNode* head = new ListNode(); head->val = 5;

所以如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！

链表的操作

删除节点

将需要删除的节点的前一个指针的next修改为指向需要删除的节点next

C++最好再手动释放需要删除的节点，Java和Python用自己的内存回收机制，不需要自己手动释放

添加节点

1.将新节点的next指针修改为新节点的前一个节点的next

2.将新节点的位置的前一个指针的next指针修改为指向新节点

性能分析

数组（长度固定，改动长度需要重新定义一个新数组）

插入/删除（时间复杂度）O(n)
查询（时间复杂度）O(1)
适用场景：数据量固定，频繁查询，较少增删

链表（长度不固定，可以动态增删）

插入/删除（时间复杂度）O(1)
查询（时间复杂度）O(n)
适用场景：数据量不固定，频繁增删，较少查询

其他语言

Java链表定义代码：

public class ListNode{
	int val;                                //节点的值
	ListNode next;                          //下一个节点
	public ListNode(){}                     //节点的构造函数（无参）
	public ListNode(int val){               //节点的构造函数（有一个参数）
		this.val = val;
	}
	public ListNode(int val,ListNode next){ //节点的构造函数（有两个参数）
		this.val = val;
		this.next = next;
	}
}

Go链表定义代码：

type ListNode struct{
	Val int
	Next *ListNode
}

203.移除链表元素

【方法一】

直接使用原来的链表来进行删除操作。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while(head != null && head.val == val){
            head = head.next;
        }
        if(head == null){
            return head;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur != null ){
            if(cur.val == val){
                pre.next = cur.next;
            }else{
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }
}

Go语言的话还需要注意语法问题，不是用null，而是nil;不是用while，而是for

func removeElements(head *ListNode, val int) *ListNode {
    for head != nil && head.Val == val{
        head = head.Next;
    }
    if(head == nil){
        return head;
    }
     pre := head;
     cur := head.Next;
    for cur != nil{
        if(cur.Val == val){
            pre.Next = cur.Next;
        }else{
            pre = cur;
        }
        cur= cur.Next;
    }
    return head;
}

【方法二】

新增一个虚拟节点

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //该段函数的作用是用于删除在首位就出现的val值，使得首节点不是val值并进行接下来的一系列操作
        while(head != null && head.val == val){
            head =head.next;
        }
        if(head == null) return head;

        ListNode dummyNode = new ListNode();
        dummyNode.next = head;
        ListNode cur = head;
        while(cur != null && cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return dummyNode.next;
    }
}

func removeElements(head *ListNode, val int) *ListNode {
    dummyHead := &ListNode{}
    dummyHead.Next = head; //new一个新的头节点
    cur := dummyHead //需要分清楚指向的是头结点
    for cur != nil && cur.Next != nil{
        if cur.Next.Val == val{
            cur.Next = cur.Next.Next
        }else{
            cur = cur.Next
        }
    }
    return dummyHead.Next
}

707.设计链表

文章：代码随想录 (programmercarl.com)

题目：707. 设计链表.url

Java实现：

class ListNode{
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val){
        this.val = val;
    }
}
class MyLinkedList {
    int size  ;
    ListNode head;
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }
    
    public int get(int index) {
        if(index <0 ||index>= size)return -1;//index非法
        ListNode dummy = head;
        for(int i = 0 ; i <= index ;i++){//没有加上=号，导致dummy没有到达正确的index位置
            dummy = dummy.next;
        }
        return dummy.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 dummy = head;
        for(int i = 0 ; i <index ; i++){//这里不不需要=号，我们需要到达其前驱
            dummy = dummy.next;
        }//到index 的前一位
        ListNode add = new ListNode(val);
        add.next = dummy.next;
        dummy.next = add;
        return ;
    }
    
    public void deleteAtIndex(int index) {
        if(index >= size || index < 0 )return;//这里也遗漏了=号，导致没有正确的判断链表的长度
        size--;//放的位置也很重要，尤其是这个后面有return，会导致数组的长度不正确！！！
        if(index ==0) {
            head = head.next;
            return;
        }
        ListNode dummy = head;
        for(int i = 0;i<index;i++){
            dummy = dummy.next;
        }
        
        dummy.next = dummy.next.next;
    }
}

Go实现

//Go库里面已经自带一个ListNode惹，我选择直接用
type MyLinkedList struct {
    SingleNode *ListNode
    Size int
}


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


func (this *MyLinkedList) Get(index int) int {
    //index非法
    if index<0 || index >= this.Size || this == nil{
        return -1;
    }
    cur := this.SingleNode
    for i := 0 ; i <= index ;i++{
        //this = this.Next 不能改变头结点！！
        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+=1
    cur := this.SingleNode
    //到index的前一个位置
    for i:= 0;i<index;i++{
        cur = cur.Next
    }
    //node := new ListNode(val) 不是这么表达的
    node := &ListNode{val,cur.Next}
    //node.Next = cur.Next
    cur.Next = node
}


func (this *MyLinkedList) DeleteAtIndex(index int)  {
    /* 这个if判断有误，应该判断的是index是否非法！！
    if this.Size == 0 || this == nil{
        return 
    }*/
    if index >= this.Size || index < 0 {
        return
    }
    this.Size -=1
    cur := this.SingleNode
    for i:= 0;i<index;i++{
        cur = cur.Next
    }
    cur.Next = cur.Next.Next

}

206.反转链表

文章：代码随想录 (programmercarl.com)

题目：206. 反转链表 - 力扣（LeetCode）

【方法一】

双指针法

class Solution {
    public ListNode reverseList(ListNode head) {
        //双指针法
        ListNode cur = head;
        ListNode pre = null;
        ListNode temp = null;
        while(cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp
        }
        return pre;
    }
}

func reverseList(head *ListNode) *ListNode {
    //双指针法
    //卡在了pre的初始化上面，多打印了一个0：[5,4,3,2,1,0]
    //最后选择先声明pre，不初始化pre
    var pre *ListNode
    cur := head
    for cur != nil{
        temp := cur.Next
        cur.Next = pre
        pre = cur
        cur = temp
    }
    return pre
}

【方法二】

递归

class Solution {
    public ListNode reverseList(ListNode head) {
        //递归
        return reverse(null,head);
    }
    public ListNode reverse(ListNode pre,ListNode cur){
        if(cur == null)return pre;

        ListNode temp = cur.next;
        cur.next = pre;

        return reverse(cur,temp);
    }
}

 //对于初始化变量这块还是不熟练，经常习惯性的写成 ListNode* pre...
func reverse( prev *ListNode, cur *ListNode) *ListNode{
    if cur == nil{
        return prev 
    }
    temp := cur.Next
    cur.Next = prev
    return reverse(cur,temp)
}
func reverseList(head *ListNode) *ListNode {
    //递归
    return reverse(nil,head)
}

【算法总结】

移除链表元素需要使用双指针OR创建一个虚拟节点来进行操作；
设计链表需要注意三点：

注意index和size在不同函数里面的比较关系；

注意index可能会出现的非法问题；

数组容量size的放置位置很关键！
反转链表需要使用双指针OR递归来进行操作。

【语言总结】

Go语言

**不是用null，而是nil; 不是用while，而是for**；

巩固了如何正确初始化一个结构体NewOne := &structName{}；

巩固了结构体内的属性需要大写才能被外部访问。

1 2	//node := new ListNode(val) 不是这么表达的 node := &ListNode{val,cur.Next}

//卡在了pre的初始化上面，多打印了一个0：[5,4,3,2,1,0]
// pre := &ListNode{0,nil}是错误的
//选择先声明pre，不初始化pre
    var pre *ListNode