Day03代码随想录2* | 链表&&移除链表元素&&设计链表&&翻转链表

时长：6h

链表理论基础

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

链表类型

单链表

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

双链表

每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点

既可以向前查询，也可以向后查询

循环链表

链表首尾相连

可解决约瑟夫环问题

【故事讲述了一群罗马士兵在被围困的要塞中，面临被敌军俘虏的命运。为了避免被俘，他们决定集体自杀。但是，他们希望通过某种方式来决定自己的死亡顺序，以避免出现任何争斗。

于是，他们决定围成一个圆圈，从某个固定的位置开始，按照一定的规则进行计数，每计到一个特定的数字，对应的士兵就会被处决，直到只剩下最后一个人幸存。

这个问题的数学形式可以描述为：给定n个人围成一个圆圈，并从编号为1的人开始报数，每次数到第m个人，就将该人处决。然后从下一个人重新开始报数，直到只剩下最后一个人。】

链表的存储方式

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

链表的定义

• 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 struct知识

type ListNode struct{
    Val int
    Next *ListNode
}

链表的操作

删除节点

删除B节点，修改A节点的next指针指向C节点即可。

添加节点

添加B节点，修改1节点的next指针等于A节点的next指针，2A节点的next指针指向B节点。

203.移除链表元素

文章：2. 移除链表元素

题目：203. 移除链表元素

【思路】

1.移除头结点== target的情况

2.移除非头结点 == target的情况

• Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //1.处理头结点 == val的情况
        while(head != null && head.val == val){
            head = head.next;
        }
        if(head == null){
            return head;
        }

        //2.处理非头节点
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while(cur != null){
            if(cur.val == val){
                pre.next = cur.next;
            }else{
                pre = cur;
            }
            cur = cur.next;
        }
        //使用虚拟头结点
        return dummy.next;
    }
}

• Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    for head!= nil && head.Val == val{
        head = head.Next
    }
    if head == nil{
        return head
    }
    //复习new结构体
    dummy := &ListNode{
        Val : -1,
        Next : head,
    }
    pre := dummy
    cur := head
    for cur != nil{
        if cur.Val == val{
            pre.Next = cur.Next
        }else{
            pre = cur
        }
        cur = cur.Next
    }
    return head

}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    dummy := &ListNode{}
    dummy.Next = head
    cur := dummy//这里 赋值为dummy 而不是dummy.Next（指多了）
    for cur != nil && cur.Next!= nil{
        if cur.Next.Val == val{
            cur.Next = cur.Next.Next
        }else{
            cur = cur.Next
        }
    }
    return dummy.Next

}

---

707.设计链表

文章：3. 设计链表

题目：707. 设计链表

【思路】

单链表

也是debug了很久，要使用一个变量存数组的长度比较方便

• Java

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;
    }

}
class MyLinkedList {
    int length;
    ListNode head;
    public MyLinkedList() {
        head = new ListNode(0);
        length = 0;
    }
    
    public int get(int index) {
        if( index <0 || length <= index)return -1;
        ListNode dummy = head;
        for(int i= 0;i <= index;i++){//查找第n+1节点
            dummy = dummy.next;
        }
        return dummy.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(length,val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index > length )return ;
        if(index <0 )index = 0;
        ListNode pre = head;
        for(int i =0 ; i < index;i++){
            pre = pre.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = pre.next;
        pre.next = newNode;
        length++;
    }
    
    public void deleteAtIndex(int index) {
        if(index >= length || index <0 )return ;
        ListNode dummy = new ListNode(-1,head);
        ListNode pre = dummy.next;
        for(int i = 0; i < index;i++){
            pre = pre.next;
        }
        pre.next = pre.next.next;
        length--;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

• Go

type Node struct{
     Val int
     Next *Node
}
type MyLinkedList struct {
     Head *Node
     Size int 
}


func Constructor() MyLinkedList {
    node := &Node{-1,nil,}
    return MyLinkedList{
        Head: node,
        Size:0,
    }
}


func (this *MyLinkedList) Get(index int) int {
    if index >= this.Size || index <0{//!
        return -1
    }
    dummy :=  this.Head
    for i :=0 ;i <= index;i++{
        dummy = dummy.Next
    }
    return dummy.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
    }
    dummy :=  this.Head
    for i:=0 ;i < index;i++{
        dummy = dummy.Next
    }
    NewNode := &Node{
        Val:val,
        Next: dummy.Next,
    }
    dummy.Next = NewNode
    this.Size++
}


func (this *MyLinkedList) DeleteAtIndex(index int)  {
    if index <0|| index >=  this.Size{  //大于等于size直接无效
        return 
    }
    dummy :=  this.Head
    for i :=0;i< index;i++{
        dummy = dummy.Next
    }
    dummy.Next = dummy.Next.Next
    this.Size--

}


/**
 * 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);
 */

双向链表

• Java

class ListNode{
    int val;
    ListNode next,prev;
      public ListNode(){
    }
    public ListNode(int val){
        this.val = val;
    }
    public ListNode(int val,ListNode next){
        this.val = val;
        this.next = next;
    }

}
class MyLinkedList {
    int length;
    ListNode head,tail;
    public MyLinkedList() {
        head = new ListNode(0);
        tail = new ListNode(0);//指示链表的上一节点
        length = 0;
        //!!
        head.next = tail;
        tail.prev = head;
    
    }
    
    public int get(int index) {
        if( index <0 || length <= index)return -1;
        ListNode dummy = head;
        //看哪边更省时间
        if(index >= length/2 ){
            dummy = tail;
            for(int i = 0;i < length - index;i++){
                dummy = dummy.prev;
            }
        }else{
            for(int i= 0;i <= index;i++){//查找第n+1节点
               dummy = dummy.next;
            }
        }
        return dummy.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(length,val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index > length )return ;
        if(index <0 )index = 0;
        ListNode pre = head;
        for(int i =0 ; i < index;i++){
            pre = pre.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = pre.next;
        newNode.prev = pre;
        pre.next.prev = newNode;
        pre.next = newNode;

        length++;
    }
    
    public void deleteAtIndex(int index) {
        if(index >= length || index <0 )return ;
        ListNode dummy = new ListNode(-1,head);
        ListNode pre = dummy.next;
        for(int i = 0; i < index;i++){
            pre = pre.next;
        }
        pre.next.next.prev = pre;
        pre.next = pre.next.next;

        length--;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

• Go

  还在改，有机会一定弄上

---

206.翻转链表

文章：4. 翻转链表

题目：206. 反转链表

【思路】

双指针法

• Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null)return head;
        ListNode pre = null;
        ListNode cur = head;
        while(cur!= null){
            ListNode node = cur.next;
            cur.next = pre;
            pre = cur;
            cur = node;
        }
        return pre;
    }
}

• Go

  对双指针不够熟练

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil{
        return head
    }
    cur := head
    var pre *ListNode
    for cur != nil{
        node:= cur.Next
        cur.Next = pre
        pre = cur
        cur = node
    }
    //届时的head只指向最后的1
    return pre
}

---

【算法总结】

对链表的具体实现还是不够熟练