Leetcode|链表

豆知识⁍

伪头！！⁍

1	`ListNode phead = new ListNode(-1, head);`

java链表基本结构⁍

class ListNode {        //类名 ：Java类就是一种自定义的数据结构
    int val;            //数据 ：节点数据 
    ListNode next;      //对象 ：引用下一个节点对象。在Java中没有指针的概念，Java中的引用和C语言的指针类似
    
    ListNode(int val){  //构造方法 ：构造方法和类名相同   
        this.val=val;     //把接收的参数赋值给当前类的val变量
    }
}

范型写法：使用范型可以兼容不同的数据类型

class ListNode<E>{                //类名 ：Java类就是一种自定义的数据结构
    E val;                        //数据 ：节点数据 
    ListNode<E> next;             //对象 ：引用下一个节点对象。在Java中没有指针的概念，Java中的引用和C语言的指针类似
    
    ListNode(E val){              //构造方法 ：构造方法和类名相同   
        this.val=val;             //把接收的参数赋值给当前类的val变量
    }
}

leetcode203中的定义

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

双链表⁍

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

回收删除⁍

在对节点进行替换或删除的时候，被替换或被删节点的next引用需不需要设置为null？

答案是： 不需要，因为一个对象被回收的前提是因为没有任何地方持有这个对象的引用（引用计数器为0）也就是说它不在被引用，那么那么它将被回收，至于它引用什么对象无关紧要，因为对于它所引用的对象来说依然是看引用计数器是否为0；^[1]

链表的递归遍历⁍

剑指 offer 06. 从尾到头打印链表

class Solution {
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] res = new int[tmp.size()];
        for(int i = 0; i < res.length; i++)
            res[i] = tmp.get(i);
        return res;
    }
    void recur(ListNode head) {
        if(head == null) return;
        recur(head.next);
        tmp.add(head.val);
    }
}

这题可以直接用循环+栈做，本质一样

基础操作：203. 移除链表元素 ⁍

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

思路：设置虚拟节点dummyNode

由于链表的头节点head 有可能需要被删除，因此创建哑节点dummyNode

class Solution {

  public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
      return head;
    }
    ListNode dummyNode = new ListNode(-1, head);
    ListNode pre = dummyNode;
    ListNode cur = head;

    while (cur != null) {//终止条件
      if (cur.val == val) {
        pre.next = cur.next;
      } else {
        pre = cur;
      }
      cur = cur.next;
    }

    return dummyNode.next;
  }
}

基础操作：707.设计链表 ⁍

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

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

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

思路

哨兵节点：

哨兵节点在树和链表中被广泛用作伪头、伪尾等，通常不保存任何数据。

我们将使用伪头来简化我们简化插入和删除。在接下来的两种方法中应用此方法。
双链表的双向搜索：我们可以从头部或尾部进行搜索。

单链表

有关ListNode的定义见leetcode203中的定义

class MyLinkedList {
  public ListNode phead; //伪头节点
  public int size;

  public MyLinkedList() {
    this.size = 0;
    this.phead = new ListNode(-1);
  }

  public int get(int index) {
    if (index < 0 || index >= size) return -1;

    ListNode cur = this.phead;
    for (int i = 0; i <= index; i++) {
      cur = cur.next;
    }

    return cur.val;
  }

  public void addAtHead(int val) {
    // ListNode newHead = new ListNode(val, this.phead.next);
    // this.phead.next = newHead;
    // this.size++;
    addAtIndex(0, val);
  }

  public void addAtTail(int val) {
    ListNode tmp = this.phead;
    while (tmp.next != null) {
      tmp = tmp.next;
    }
    tmp.next = new ListNode(val);
    this.size++;
    // addAtIndex(this.size, val);
  }

  public void addAtIndex(int index, int val) {
    if (index > this.size) return;

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

    this.size++;

    ListNode pre = phead;
    for (int i = 0; i < index; i++) {
      pre = pre.next;
    }
    ListNode newNode = new ListNode(val, pre.next);
    pre.next = newNode;
  }

  public void deleteAtIndex(int index) {
    if (index < 0 || index >= this.size) return;
    this.size--;

    ListNode pre = phead;
    for (int i = 0; i < index; i++) {
      pre = pre.next;
    }
    pre.next = pre.next.next;
  }
}

双链表

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

2. 两数相加 ⁍

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

1
2
3

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

思路/试错

一开始用int sum来存储数据，通过sum+=val*i;i*=10类似的方法来更新sum；然后再通过不断%10来把每一位加入链表

这样会有问题，当数据太大的时候，因为int类型长度有限，会发生溢出

Testcase

1 2	`[9] [1,9,9,9,9,9,9,9,9,9]`

Answer

1	`[8,0,4,5,6,0,0,1,4,1]`

Expected Answer

1	`[0,0,0,0,0,0,0,0,0,0,1]`

而且要多写一次循环=。=

在加的过程中就建链表

注意最后的进位要处理

class Solution {

  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

    //新链表
    ListNode newPHead = new ListNode();
    ListNode pre = newPHead;
    int c = 0; //记进位
    int sum = 0; //和


    while (l1 != null || l2 != null) {
      int n1 = l1 != null ? l1.val : 0;
      int n2 = l2 != null ? l2.val : 0;

      sum = n1 + n2 + c; //加进位
      if (sum >= 10) {
        c = 1; //设进位是1
        sum %= 10;
      } else {
        c = 0;
      }
      //添加新节点
      ListNode newNode = new ListNode(sum);
      pre.next = newNode;
      pre = newNode;
      //后移两个节点
      if (l1 != null) {
        l1 = l1.next;
      }
      if (l2 != null) {
        l2 = l2.next;
      }
    }

    //处理最后的进位
    if (c == 1) {
      ListNode newNode = new ListNode(1);
      pre.next = newNode;
      pre = newNode;
    }

    return newPHead.next;
  }
}

19. 删除链表的倒数第 N 个结点 ⁍

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

思路： 快慢指针

class Solution {

  public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode phead = new ListNode(-1, head); //伪头
    ListNode slow = phead;
    ListNode fast = phead;
    //移动fast节点，让它领先slow，因为1 <= n <= sz，所以不必考虑非法错误
    for (int i = 0; i < n; i++) {
      fast = fast.next;
    }
    while (fast.next != null) {
      fast = fast.next;
      slow = slow.next;
    }
    slow.next = slow.next.next;
    return phead.next;
  }
}

23. 合并K个升序链表 ⁍

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

思路一： 在21.合并两个有序链表的基础上改进，两两合并

可以依次遍历，但更好的方法是分治（类二分法）

按[left,mid]，[mid+1,right]进行划分
left==right时，返回list[left]
left>right时，返回null，递归终止

class Solution {

  //分治法，
  public ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;

    return merge(lists, 0, lists.length - 1);
  }

  public ListNode merge(ListNode[] lists, int l, int r) {
    if (l < r) {
      int mid = (r + l) >> 1;
      return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    } else if (l == r) {
      return lists[l];
    }
    return null;
  }

  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    //注意两个链表的节点数目范围从0开始

    ListNode pnewList = new ListNode();
    ListNode cur = pnewList;
    while (list1 != null && list2 != null) {
      int n1 = list1.val;
      int n2 = list2.val;
      if (n1 < n2) {
        cur.next = list1;
        list1 = list1.next; //向后挪
      } else {
        cur.next = list2;
        list2 = list2.next;
      }

      cur = cur.next;
    }
    cur.next = list1 == null ? list2 : list1;

    return pnewList.next;
  }
}

思路二：使用优先队列合并

即每个链表没有被合并的元素的最前面一个，每次在这些元素里面选取 val 属性最小的元素合并到答案中。

用优先队列优化合并K个排序链表 - 合并K个升序链表 - 力扣（LeetCode） (leetcode-cn.com)

PriorityQueue和Queue的区别在于，它的出队顺序与元素的优先级有关，对PriorityQueue调用remove()或poll()方法，返回的总是优先级最高的元素。

要使用PriorityQueue，我们就必须给每个元素定义“优先级”。

使用PriorityQueue - 廖雪峰的官方网站 (liaoxuefeng.com)

class Solution {
    class Status implements Comparable<Status> {
        int val;
        ListNode ptr;

        Status(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }

        public int compareTo(Status status2) {
            return this.val - status2.val;
        }
    }

    PriorityQueue<Status> queue = new PriorityQueue<Status>();

    public ListNode mergeKLists(ListNode[] lists) {
        for (ListNode node: lists) {
            if (node != null) {
                queue.offer(new Status(node.val, node));
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!queue.isEmpty()) {
            Status f = queue.poll();
            tail.next = f.ptr;
            tail = tail.next;
            if (f.ptr.next != null) {
                queue.offer(new Status(f.ptr.next.val, f.ptr.next));
            }
        }
        return head.next;
    }
}

141. 环形链表 ⁍

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

// pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

// pos 是给我们自定义测试案例的

思路： 快慢指针

慢指针步长1，快指针步长2，如果是环形链表，快指针一定能追上慢指针

public class Solution {

  public boolean hasCycle(ListNode head) {
    // pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
    // pos 是给我们自定义测试案例的
    if (head == null || head.next == null) return false;

    ListNode slowp = head; //慢指针
    ListNode fastp = head; //快指针

    //慢指针步长1，快指针步长2，如果是环形链表，快指针
    while (fastp != null && fastp.next != null) {
      slowp = slowp.next;
      fastp = fastp.next.next;
      if (slowp == fastp) {
        return true;
      }
    }
    return false;
  }
}

142. 环形链表 II ⁍

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

不允许修改 链表。

思路一：用Set存节点

public class Solution {

  public ListNode detectCycle(ListNode head) {

    Set<ListNode> nodes = new HashSet<>();
    while (head != null) {
      if (!nodes.add(head)) {
        return head;
      }

      head = head.next;
    }
    return null;
  }
}

思路二：快慢指针

在141的基础上，通过计算来得到相应的节点

fig1

慢指针和快指针相遇时：慢指针走了$a+b$，快指针走了$a+n(b+c)+b$，则

$$2(a+b)=a+n(b+c)+b$$

即

$$a=(n-1)(b+c)+c$$

新设一个指针newp，从head开始和慢指针一起移动，则最后一定会在入口处相遇

public class Solution {

  public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) {
      return null;
    }
    ListNode slowp = head;
    ListNode fastp = head;
    while (fastp != null && fastp.next != null) {
      slowp = slowp.next;
      fastp = fastp.next.next;
      if (slowp == fastp) {
        ListNode newp = head;
        while (slowp != newp) {
          slowp = slowp.next;
          newp = newp.next;
        }
        return newp;
      }
    }
    return null;
  }
}

[java ListNode 链表 - 一文搞懂 - 博客园 (cnblogs.com)](https://www.cnblogs.com/easyidea/p/13371863.html#:~:text=链表是一种数据结构：由数据和指针构成，链表的指针指向下一个节点。 java,ListNode 链表就是用Java自定义实现的链表结构。) ↩︎

豆知识⁍

伪头！！⁍

java链表基本结构⁍

双链表⁍

回收删除⁍

链表的递归遍历⁍

基础操作：203. 移除链表元素⁍

基础操作：707.设计链表⁍

2. 两数相加⁍

19. 删除链表的倒数第 N 个结点⁍

23. 合并K个升序链表⁍

141. 环形链表⁍

142. 环形链表 II⁍