我的第一篇博客—从HelloWorld谈起

链表

1. 有序的列表，但是在内存上是不一定连续的，以节点的形式存储，每个节点包含data和next，分为带头节点和不带头节点，是一种线性结构，大多数情况下采用头节点描述整个链表
2. 分类

• 单链表

  • 增删改查实现（遍历时间O（n）,插入时间O（1),删除O（n））

  package com.atguigu.com.xiti;
  
  public class demo {
      public static void main(String[] args) {
          linkList<Integer> l = new linkList<>();
          l.addFirst(1);
          l.addFirst(2);
          l.addFirst(3);
          l.addFirst(4);
          l.delete(2);
          l.remove(3);
         // l.show();
          System.out.println(l.query(1));;
          l.update(4, 5);
          l.show();
      }
  }
  
  /*单链表：
   * 创建、修改、删除、显示等等*/
  class linkList<T> {
      private Node head;//头节点但不是虚拟的头节点是实际存在的链表首节点
      private int size;
  
      //链表节点的实体类
      class Node<T> {
          public T val;
          public Node next;
  
          public Node(T val) {
              this.val = val;
          }
  
          public Node(T val, Node next) {
              this.val = val;
              this.next = next;
          }
      }
  
      //增加:分为头插尾插和中间插入
      //头部添加
      public void addFirst(T x) {
          Node node = new Node(x);
          node.next = head;
          head = node;
          size++;
      }
  
      //尾部插入
      public void addLast(T x) {
          addMid(x, size);
      }
  
      //中间插入
      public void addMid(T x, int index) {
          if (index < 0 || index > size) {
              throw new IllegalArgumentException("插入位置错误");
          }
          if (index == 0) {
              addFirst(x);
          }
          Node pre = head;
          for (int i = 0; i < index - 1; i++) {
              pre = pre.next;
          }
          Node node = new Node(x);
          node.next = pre.next;
          pre.next = node;
          size++;
      }
  
      //以上是基于索引的插入
      //虚拟头节点的插入，基于插入元素
      public void virAdd(T tag, T x) {
          Node dummy = new Node(null, head);
          Node cur = dummy;
          Node node = new Node(x);
          while (cur.next != null) {
              if (cur.next.val.equals(tag)) {
                  node.next = cur.next;
                  cur.next = node;
                  size++;
                  break;
              } else cur = cur.next;
          }
          head = dummy.next;
      }
  
      //采用虚拟头节点的删除
      public void delete(T x) {
          Node dummy = new Node(null, head);
          Node cur = dummy;
          while (cur.next != null) {
              if (cur.next.val.equals(x)) {
                  cur.next = cur.next.next;
                  size--;
              } else cur = cur.next;
          }
          head = dummy.next;
      }
  
      //删除头部元素尾部元素和不采用虚拟节点
      public T removeFirst() {
          if (head == null) {
              System.out.println("没有元素可以删除");
              return null;
          }
          Node del = head;
          head = head.next;
          del.next = null;
          size--;
          return (T) del.val;
      }
  
      public T removeLast() {
          if (head == null) {
              System.out.println("没有元素可以删除");
              return null;
          }
          if (size == 1) {
              return removeFirst();
          }
          Node pre = head;
          Node cur = head;
          while (cur.next != null) {
              pre = cur;
              cur = cur.next;
          }
          pre.next = cur.next;
          size--;
          return (T) cur.val;
      }
  
      public void remove(T x) {
          if (head == null) {
              System.out.println("没有元素可以删除");
              return;
          }
          while (head != null && head.val.equals(x)) {
              head = head.next;
              size--;
          }
          Node cur = head;
          while (cur != null && cur.next != null) {
              if (cur.next.val.equals(x)) {
                  cur.next = cur.next.next;
                  size--;
              } else cur = cur.next;
          }
      }
  
      //修改
      public void update(T tag, T val) {
          if (head == null) {
              System.out.println("链表为空");
              return;
          }
          Node cur = head;
          while (cur != null) {
              if (cur.val == tag) {
                  cur.val = val;
                  // cur = cur.next;
              }
              cur = cur.next;
          }
      }
  
      //查找
      public boolean query(T x) {
          Node cur = head;
          while (cur != null) {
              if (cur.val.equals(x)) {
                  return true;
              } else cur = cur.next;
          }
          return false;
      }
  
      public void show() {
          if (head == null) {
              System.out.println("链表为空，无法遍历");
          }
          Node cur = head;
          while (cur != null) {
              System.out.println(cur.val);
              cur = cur.next;
          }
      }
  }

相关题目

1.LC707-设计链表

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

• 不采用头节点

class MyLinkedList {
    class Node{
        public int val;
        public Node next;
        public Node(int val){
            this.val=val;
        }
    }
    public int size;//代表链表的长度
    public Node head;//链表的头节点，注意不是虚拟节点，默认为null，若要采用虚拟节点，自行构造器中赋值
    /** Initialize your data structure here. */
    public MyLinkedList() {
    }
    //注意这里的index是从零开始的，后面每个方法都要注意节点的索引
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        if(index<0||index>size-1)return -1;
        Node res=head;
        for(int i=0;i<index;i++){
            res=res.next;
        }
        return res.val;
    }
    
    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        Node node=new Node(val);
        node.next=head;
        head=node;
        size++;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        Node node=new Node(val);
        Node tmp=head;
        if(head==null){
            head=node;
            size++;
            return;
        }
        while(tmp.next!=null){
            tmp=tmp.next;
        }
        tmp.next=node;
        size++;
    }
    
    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        
        if(index<=0){
            addAtHead(val);
            size++;
            return;
        }
        if(index>size)return;
        Node pre=head;
        Node tmp=new Node(val);
        for(int i=0;i<index-1;i++){
            pre=pre.next;
        }
        tmp.next=pre.next;
        pre.next=tmp;
        size++;
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        if(index<0||index>size-1)return;
        Node pre=head;
        if(index==0){
            head=head.next;
            size--;
            return;
        }
        for(int i=0;i<index-1;i++){
            pre=pre.next;
        }
        pre.next=pre.next.next;
        size--;
    }
}

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

• 采用头节点

public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}

class MyLinkedList {
  int size;
  ListNode head;  // sentinel node as pseudo-head
  public MyLinkedList() {
    size = 0;
    head = new ListNode(0);
  }

  /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
  public int get(int index) {
    // if index is invalid
    if (index < 0 || index >= size) return -1;

    ListNode curr = head;
    // index steps needed 
    // to move from sentinel node to wanted index
    for(int i = 0; i < index + 1; ++i) curr = curr.next;
    return curr.val;
  }

  /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
  public void addAtHead(int val) {
    addAtIndex(0, val);
  }

  /** Append a node of value val to the last element of the linked list. */
  public void addAtTail(int val) {
    addAtIndex(size, val);
  }

  /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
  public void addAtIndex(int index, int val) {
    // If index is greater than the length, 
    // the node will not be inserted.
    if (index > size) return;

    // [so weird] If index is negative, 
    // the node will be inserted at the head of the list.
    if (index < 0) index = 0;

    ++size;
    // find predecessor of the node to be added
    ListNode pred = head;
    for(int i = 0; i < index; ++i) pred = pred.next;

    // node to be added
    ListNode toAdd = new ListNode(val);
    // insertion itself
    toAdd.next = pred.next;
    pred.next = toAdd;
  }

  /** Delete the index-th node in the linked list, if the index is valid. */
  public void deleteAtIndex(int index) {
    // if the index is invalid, do nothing
    if (index < 0 || index >= size) return;

    size--;
    // find predecessor of the node to be deleted
    ListNode pred = head;
    for(int i = 0; i < index; ++i) pred = pred.next;

    // delete pred.next 
    pred.next = pred.next.next;
  }
}

2.单链表的有效节点个数（带头节点需要去除头节点）

public int getLength(Node node){
	if(node.next==null)return 0;
	int count=0;
	Node cur=node.next;
	while(cur!=null){
		cur=cur.next;
		count++;
	}
		return count;
}

3.链表的倒数第K个节点

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        int c=getLength(head);
        if(k<=0||k>c)return null;
        ListNode cur=head;
        for(int i=0;i<c-k;i++){
            cur=cur.next;
        }
        return cur;
    }
    public int getLength(ListNode head){
        if(head==null)return 0;
        int count=0;
        while(head!=null){
            head=head.next;
            count++;
        }
        return count;
    }
}

4.反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur=head,pre=null;
        while(cur!=null){
            ListNode tmp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
}
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode dummy=new ListNode(-1);
        ListNode cur=head;
        while(cur!=null){
            ListNode tmp=cur;
            cur=cur.next;
            tmp.next=dummy.next;
            dummy.next=tmp;
        }
        return dummy.next;
    }
}
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null)return head;
        ListNode tmp=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return tmp;

    }
}

5.链表中的双指针问题

• 应用场景

  • 不同位置出发：头部和尾部
  • 不同速度移动：快慢指针问题

• 环形链表

  • 一定相遇：常识
  • 相遇时慢指针并没有绕环超过一周：慢指针入环时快指针相距m，一定小于环长度，再走m步一定追上慢指针
  • 入环节点的寻找，先找相遇点，然后从相遇点和头节点同步走：a+b+nc=2(a+b)得出a=(n-1)(b+c)+c
  • 为什么是两倍，不是三倍等，算法效率最高

• 判断链表是否有环

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null)return false;
        ListNode fast=head,slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)return true;
        }
        return false;
    }
}

• 找出链表中的入环节点

public class Solution {
    public ListNode detectCycle(ListNode head) {
        boolean res=hasCycle(head);
        if(!res)return null;
        ListNode fast=head,slow=head;
        while(fast!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)break;
        }
        fast=head;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null)return false;
        ListNode fast=head,slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)return true;
        }
        return false;
    }
}

• 删除链表倒数第K个节点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int c=getLength(head);
        if(n>c||n<0)return null;
        if(n==c)return head.next;
        ListNode slow=head;
        for(int i=0;i<c-n-1;i++){
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return head;
    }
    public int getLength(ListNode head){
        if(head==null||head.next==null)return 0;
        ListNode cur=head;
        int c=0;
        while(cur!=null){
            cur=cur.next;
            c++;
        }
        return c;
    }
}

• 回文链表

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null)return true;
        ListNode fast=head,slow=head;
        ListNode pre=head,p=null;
        while(fast!=null&&fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
            pre.next=p;
            p=pre;
        }
        if(fast!=null)slow=slow.next;
        while(pre!=null&&slow!=null){
            if(pre.val!=slow.val)return false;
            slow=slow.next;
            pre=pre.next;
        }
        return true;
    }
}

6.设计双链表

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

public class ListNode {
  int val;
  ListNode next;
  ListNode prev;
  ListNode(int x) { val = x; }
}

class MyLinkedList {
  int size;
  // sentinel nodes as pseudo-head and pseudo-tail
  ListNode head, tail;
  public MyLinkedList() {
    size = 0;
    head = new ListNode(0);
    tail = new ListNode(0);
    head.next = tail;
    tail.prev = head;
  }

  /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
  public int get(int index) {
    // if index is invalid
    if (index < 0 || index >= size) return -1;

    // choose the fastest way: to move from the head
    // or to move from the tail
    ListNode curr = head;
    if (index + 1 < size - index)
      for(int i = 0; i < index + 1; ++i) curr = curr.next;
    else {
      curr = tail;
      for(int i = 0; i < size - index; ++i) curr = curr.prev;
    }

    return curr.val;
  }

  /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
  public void addAtHead(int val) {
    ListNode pred = head, succ = head.next;

    ++size;
    ListNode toAdd = new ListNode(val);
    toAdd.prev = pred;
    toAdd.next = succ;
    pred.next = toAdd;
    succ.prev = toAdd;
  }

  /** Append a node of value val to the last element of the linked list. */
  public void addAtTail(int val) {
    ListNode succ = tail, pred = tail.prev;

    ++size;
    ListNode toAdd = new ListNode(val);
    toAdd.prev = pred;
    toAdd.next = succ;
    pred.next = toAdd;
    succ.prev = toAdd;
  }

  /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
  public void addAtIndex(int index, int val) {
    // If index is greater than the length, 
    // the node will not be inserted.
    if (index > size) return;

    // [so weird] If index is negative, 
    // the node will be inserted at the head of the list.
    if (index < 0) index = 0;

    // find predecessor and successor of the node to be added
    ListNode pred, succ;
    if (index < size - index) {
      pred = head;
      for(int i = 0; i < index; ++i) pred = pred.next;
      succ = pred.next;
    }
    else {
      succ = tail;
      for (int i = 0; i < size - index; ++i) succ = succ.prev;
      pred = succ.prev;
    }

    // insertion itself
    ++size;
    ListNode toAdd = new ListNode(val);
    toAdd.prev = pred;
    toAdd.next = succ;
    pred.next = toAdd;
    succ.prev = toAdd;
  }

  /** Delete the index-th node in the linked list, if the index is valid. */
  public void deleteAtIndex(int index) {
    // if the index is invalid, do nothing
    if (index < 0 || index >= size) return;

    // find predecessor and successor of the node to be deleted
    ListNode pred, succ;
    if (index < size - index) {
      pred = head;
      for(int i = 0; i < index; ++i) pred = pred.next;
      succ = pred.next.next;
    }
    else {
      succ = tail;
      for (int i = 0; i < size - index - 1; ++i) succ = succ.prev;
      pred = succ.prev.prev;
    }

    // delete pred.next 
    --size;
    pred.next = succ;
    succ.prev = pred;
  }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1293102962@qq.com