JavaSE_05_顺序表与链表

目录

• • • • 包（package）
      • • 包的命名规则
        • 包存在的意义
        • import
    • 线性表（linear list）
    • • • • 逻辑连续
          • 物理连续
      • 动态数组
      • • • 数组的size和length
        • 增删改查
        • • 补充
      • 链表
      • • 单向链表
        • • 不带头单链表
          • 删除链表所有值为val的元素
          • 带头单链表
        • 练习题
        • • [83. 删除排序链表中的重复元素](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/)
          • [82. 删除排序链表中的重复元素 II](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/)
          • [876. 链表的中间结点](https://leetcode-cn.com/problems/middle-of-the-linked-list/)
          • [206. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list/)
          • [剑指 Offer 22. 链表中倒数第k个节点](https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)
          • [234. 回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/)
          • [92. 反转链表 II](https://leetcode-cn.com/problems/reverse-linked-list-ii/)
          • [21. 合并两个有序链表](https://leetcode-cn.com/problems/merge-two-sorted-lists/)
          • [面试题 02.04. 分割链表](https://leetcode-cn.com/problems/partition-list-lcci/)
          • [160. 相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/)
          • [141. 环形链表](https://leetcode-cn.com/problems/linked-list-cycle/)
          • [142. 环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/)
          • [25. K 个一组翻转链表](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/)
        • 双向链表
        • • 增删改查

包（package）

包实际上就是文件夹，包访问权限就是当前文件夹里面可见。权限修饰符什么也没写，就是包访问权限。对于包访问权限，只有在当前文件夹内部是可见的，子包也是不可见的，只有同级目录才是可见的。

包的命名规则

字母全小写，多个单词之间用下划线分隔

包存在的意义

类可以重名，类的全名称为：包名.类名（类似文件的全名称为：文件路径+文件名+文件后缀）。

import

只能导入某个包中的某个类

线性表（linear list）

n个具有相同类型数据的有限序列，逻辑上呈直线排列，逻辑上连续，这种结构称为线性表。

常见的线性表有数组（顺序表）、链表、栈、队列、字符串……

逻辑连续

1号元素在2号元素之前，这种先后顺序指的是逻辑上的先后，物理上不一定连续（存储在内存时，不一定是连续存储）

物理连续

是指元素存储在内存上时，地址的分配一个挨一个，元素间没有存储空间上的空隙，比如数组。物理不连续的数据结构比如链表。

动态数组

一旦一个数组在定义时长度确定了，使用过程中无法修改这个长度。动态数组就是在普通数组上加上一个可以根据元素个数动态调整数组大小的功能。

Java中提供的数组都是静态数组，需要我们自己定义一个类，拓展数组的功能。

class MyArr{private int[] arr;private int size;}

当arr数组满了，存不下的时候，使用Arrays.copyOf(arr,size*2)得到新数组,将其数组容量变为原来的两倍。

数组的size和length

arr = new int[3];    //当前数组还没有存储一个有效元素，size==0.size表示当前数组中有效元素的个数。int size = 0；

新增元素到数组时，arr[size ++] = 新元素的值。

增删改查

点此查看源码

补充

System.err.println();    //错误提示

一个方法或者属性是否需要添加static关键字的本质：是否需要该类的所有对象共享这个变量

链表

单向链表

不带头单链表

这里的不带头节点指的是不带虚拟头节点(dummyhead，dummyhead不存储值，dummyhead.next指向第一个存值的节点）,以第一个节点为头节点。

每个节点只保存了下一个节点的地址，只能从头节点开始向后遍历。

class Node{    int val;    Node next;}class SingleLinkList{    private Node head;    //头节点    private int size;    //元素个数    //头插入 //遍历，实现toString方法 //在链表的index位置插入一个新元素val,关键点是找到索引为Index- 1的节点，假设该节点为pre,要插入的节点为node,则先执行：node.next = pre.next，再执行：pre.next = node.    //判断索引合法性    private boolean rangeCheck(int index){ if(index < 0 || index > size){     return false; }else{     return true; }    } public void add(int index, int val){ //判断索引合法性 //找pre //插入    }    //删除    //void remove(int index)    //void removeValOnce(int val)    //void removeAllVal(int val)    //遍历和递归实现    //查找    //boolean contains(int val)    //int get(int index)    //int getByValue(int val)    //修改    //void set(int index, int newVal)}

增删改查

点此查看源码

删除链表所有值为val的元素

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; while(pre.next != null){     if(pre.next.val == val){  pre.next = pre.next.next;     }else{  pre = pre.next;     } } return head;    }}//递归解法class Solution {    public ListNode removeElements(ListNode head, int val) { if(head == null){     return null; } head.next = removeElements(head.next, val); if(head.val == val){     return head.next; }else{     return head; }    }}

IDEA中对于选中代码进行自动对齐的快捷键：Ctrl+Alt+L

带头单链表

虚拟头节点dummy head,带头单链表对应的节点索引编号也是从0开始，并且索引从第一个有效节点开始编号（dummyHead没有索引）

练习题

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

83. 删除排序链表中的重复元素

遍历解法

class Solution {    public ListNode deleteDuplicates(ListNode head) { if(head == null){     return head; } ListNode pre = head; while(pre.next != null){     if(pre.val == pre.next.val){  pre.next = pre.next.next;     }else{  pre = pre.next;     } } return head;    }}

递归解法

class Solution {    public ListNode deleteDuplicates(ListNode head) { if(head == null){     return head; } head.next = deleteDuplicates(head.next); if(head.next == null){     return head; } if(head.val == head.next.val){     head = head.next;     return head; }else{     return head; }    }}

82. 删除排序链表中的重复元素 II

解法一：三指针

class Solution {    public ListNode deleteDuplicates(ListNode head) { if(head == null || head.next == null){     return head; } ListNode dummyHead = new ListNode(); dummyHead.next = head; ListNode pre = dummyHead, cur = pre.next, next = cur.next; while(next != null){     if(cur.val != next.val){    //cur为不重复元素，三指针后移一位，将cur收入pre,pre管着所有不重复出现的节点  pre.next = cur;  pre = pre.next;  cur = cur.next;  next = next.next;     }else{    //cur为重复元素，让next一直后移，直到next指向null或cur和next的值不相同，此时删除cur到next前一个节点，让cur指向next,next指向next的下一位，重复判断cur和next是否相等。  while(next != null && cur.val == next.val){      next = next.next;  }  if(next == null){      pre.next = null;      return dummyHead.next;  }  cur = next;  next = next.next;     } } //最后剩下一个链表最末尾的cur没有判断，将cur直接连接到pre后面 pre.next = cur; return dummyHead.next;    }}

三指针精简版

/* public class ListNode {    int val;    ListNode next = null;    ListNode(int val) { this.val = val;    }}*///用pHead这一个指针分类重复元素和非重复元素，用tail接受非重复元素。public class Solution {    public ListNode deleteDuplication(ListNode pHead) { ListNode dummyHead = new ListNode(-1); ListNode tail = dummyHead; while(pHead != null){     if(pHead.next == null || pHead.val != pHead.next.val){  tail.next = pHead;  tail = pHead;     }     while(pHead.next != null && pHead.val == pHead.next.val){  pHead = pHead.next;     }     pHead = pHead.next; } tail.next = null; return dummyHead.next;    }}

解法二：递归

class Solution {    public ListNode deleteDuplicates(ListNode head) { if(head == null || head.next == null){     return head; } //双指针找到不是重复节点的新头 ListNode pre = head, cur = head.next; while(cur != null){     if(cur.val != pre.val){  head = pre;  head.next = deleteDuplicates(head.next);  return head;     }else{  while(cur != null && cur.val == pre.val){      cur = cur.next;  }  if(cur == null){      return null;  }  pre = cur;  cur = cur.next;     } } //pre变为cur以后，若退出循环，则pre是一个没有被判断的节点，且不是重复元素，此时当前链表只有一个pre,返回它即可。 return pre;    }}

快慢指针

引入两个引用，让一个引用先走或多走几步,这样两个指针的相对距离就固定了；或者让一个指针的速度比另一个指针快，这样两个指针走过的距离之差是线性增长的。

876. 链表的中间结点

class Solution {    public ListNode middleNode(ListNode head) { ListNode low = head, fast = head; while(fast != null && fast.next != null){     fast = fast.next.next;     low = low.next; } return low;    }}

206. 反转链表

解法一：一边读取链表的节点值，一边将其用头插入的方式存到新链表中,额外空间复杂度：O(N)

class Solution {    public ListNode reverseList(ListNode head) { if(head == null || head.next == null){     return head; } ListNode newHead = null; ListNode node = head; for(; node != null; node = node.next){     ListNode newNode = new ListNode(node.val);     newNode.next = newHead;     newHead = newNode; } return newHead;    }}

解法二：不开辟新链表

解法三：递归

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

//递归class Solution {    public ListNode reverseList(ListNode head) { if(head == null || head.next == null){     return head; } ListNode node = head.next;; head.next = null; ListNode reHead = reverseList(node); node.next = head; return reHead;    }}

剑指 Offer 22. 链表中倒数第k个节点

class Solution {    public ListNode getKthFromEnd(ListNode head, int k) { //fast领先low k个步长 int count = 0; for(ListNode node = head; node != null; node = node.next, count ++){} if(k < 1 || k > count){     return null;    //表示k不符合题意 } ListNode fast = head, low = head; for(int i = 0; i < k; ++i){     fast = fast.next;    //先让fast走k步，这样fast-k始终是low } while(fast != null){     fast = fast.next;     low = low.next;    //保持k个步长的相对距离，两个指针同步走 } return low;    }}

234. 回文链表

//O(N)额外空间复杂度：先得到反转链表，再一一对比class Solution {    public boolean isPalindrome(ListNode head) { if(head == null){     return false; } ListNode newHead = reverseList(head); ListNode node1 = head; ListNode node2 = newHead; while(node1 != null && node2 != null){     if(node1.val != node2.val){  return false;     }     node1 = node1.next;     node2 = node2.next; } return true;    }    public ListNode reverseList(ListNode head){ ListNode newHead = null; ListNode cur = head; while(cur != null){     ListNode node = new ListNode(cur.val);     node.next = newHead;     newHead = node;     cur = cur.next; } return newHead;    }}

//O(1)额外空间复杂度：找中间节点+后半段反转class Solution {    public boolean isPalindrome(ListNode head) { //找中点、逆序、比较 if(head.next == null){     return true; } //找中点 ListNode fast = head.next, low = head; while(fast != null && fast.next != null){     fast = fast.next.next;     low = low.next; } //从low.next->end逆序 ListNode pre = null, cur = low.next; low.next = null; while(cur != null){     ListNode next = cur.next;     cur.next = pre;     pre = cur;     cur = next; } //head->low;pre->null遍历比较 ListNode p1 = head, p2 = pre; while(p1 != null && p2 != null){     if(p1.val != p2.val){  return false;     }     p1 = p1.next;     p2 = p2.next; } return true;    }}

92. 反转链表 II

//双指针+头插class Solution {    public ListNode reverseBetween(ListNode head, int left, int right) {//left和right从1开始编号 ListNode dummyHead = new ListNode(); dummyHead.next = head; ListNode pre = dummyHead; //pre从虚拟头节点出发，走left-1步到达left的前一个节点 for(int i = 0; i < left - 1; ++i){     pre = pre.next; } //cur节点一开始指向left位置，不断地把cur节点的下一个节点头插入，插入的位置总是pre.next，在将cur.next插入到pre.next前，开辟新节点保存cur.next的值，再把cur.next接到cur.next.next上，循环right - left次 ListNode cur = pre.next; for(int i = 0; i < right - left; ++i){     ListNode node = new ListNode(cur.next.val);     cur.next = cur.next.next;     node.next = pre.next;     pre.next = node; } return dummyHead.next;    }}

//回溯法（较难理解）class Solution {    public ListNode reverseBetween(ListNode head, int left, int right) { //这个函数递归的思想就是把left->right区间整体前移，直到left==1时，变为反转前(right-left+1)个节点，前移的手段就是在递推过程中，外层函数的head.next指向内层函数的返回值 if(left == 1){     return reverseN(head,right); } head.next = reverseBetween(head.next, left - 1, right - 1); return head;    }    ListNode behind;    //behind表示right节点的下一个节点    public ListNode reverseN(ListNode head, int n){ if(n == 1){     behind = head.next;     return head; } ListNode next = head.next;    // ListNode newHead = reverseN(head.next, n - 1); next.next = head;    // head.next = behind;    //,从n==1时，开始回溯，真正发挥反转作用就是编号为这三行代码,相当于在不断往newHead开头的链表尾插。 return newHead;    }}

21. 合并两个有序链表

//双引用遍历class Solution {    public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if(list1 == null && list2 == null){     return null; } if(list1 == null){     return list2; } if(list2 == null){     return list1; } ListNode dummyHead = new ListNode(); ListNode tail = dummyHead, p1 = list1, p2 = list2; while(p1 != null && p2 != null){     if(p1.val <= p2.val){  tail.next = p1;  p1 = p1.next;     }else{  tail.next = p2;  p2 = p2.next;     }     tail = tail.next; } if(p1 == null){     tail.next = p2; }else{     tail.next = p1; } return dummyHead.next;    }}//递归class Solution {    public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if(list1 == null && list2 == null){     return null; } if(list1 == null){     return list2; } if(list2 == null){     return list1; } if(list1.val <= list2.val){     list1.next = mergeTwoLists(list1.next, list2);     return list1; }else{     list2.next = mergeTwoLists(list2.next, list1);     return list2; }    }}

面试题 02.04. 分割链表

class Solution {    public ListNode partition(ListNode head, int x) { ListNode min = new ListNode(); ListNode max = new ListNode();    //创建两个虚拟头节点存储大于等于和小于x的值 ListNode smallTail = min, bigTail = max, node = head; while(node != null){     if(node.val < x){  smallTail.next = node;  smallTail = smallTail.next;     }else{  bigTail.next = node;  bigTail = bigTail.next;     }     node = node.next; } smallTail.next = max.next;    //合并两个链表 bigTail.next = null; return min.next;    }}

160. 相交链表

相交指的是指向同一个引用，即从该相交节点往后都只有一条路径了

假如链表A的不相交部分长度为a,链表B的不相交部分长度为b,两个链表的相交部分长度为c(若不相交，则c为0)，那么a + c + b == b + c + a .用两个指针a,b分别从headA 和 headB开始遍历两个链表，两个指针同步前进，a走完链表A时，从headB开始走，b同理，则它们有两次机会可能走到同一个节点：

1.若a == b 且 c != 0,那么当两个指针走到一起时返回该指针；

2.若a != b,那么如果它们存在交点，一定会是一个指针先走过该交点。拿上图举例：指针a因为只用走两个节点就可以到交点，而指针b需要走过三个节点才能到，所以a和b第一次会错过；那么，为了让它们再有可能相遇，两个指针重走一遍对方走过的路，这样做是为了消除在走到交点前因为各自走过的路不一样长而产生的错位，这样一来两个指针走过的节点都是a + b + c,此时它们指向交点。若没有交点，则它们都指向null.

综上，让a,b遍历，它们相等（指向同一个节点）时停止遍历，返回任意一个指针。相等有两种可能：1.都指向null->没有交点；2.指向交点。

public class Solution {    public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode a = headA, b = headB; while(a != b){     a = a == null ? headB : a.next;     b = b == null ? headA : b.next; } return a;    }}

141. 环形链表

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

142. 环形链表 II

public class Solution {    public ListNode detectCycle(ListNode head) { ListNode fast = head, low = head, p = head; if(head == null || head.next == null){     return null; } while(fast != null && fast.next != null){     fast = fast.next.next;     low = low.next;     if(fast == low){  while(low != p){      p = p.next;      low = low.next;  }  return p;     } } return null;    }}

25. K 个一组翻转链表

class Solution {    public ListNode reverseKGroup(ListNode head, int k) { if(head.next == null || k <= 1){     return head; } //先来一轮k个节点的反转 ListNode dummyHead = new ListNode(); ListNode pre = null, cur = head, begin = head, end; for(int i = 1; i <= k; i++){     ListNode next = cur.next;     cur.next = pre;     pre = cur;     cur = next; } dummyHead.next = pre;    //确定最终返回的头节点 begin.next = cur;    //将第一段反转，并与后续节点连接起来 end = begin;    //end是上一段反转后的最后一个节点 while(cur != null){     ListNode node = cur;     for(int i = 1; i <= k; i ++){  if(node == null){      return dummyHead.next;  }  node = node.next;     }//找到下一段有k个节点可以反转     pre = node;     begin = cur;     for(int i = 1; i <= k; i++){  ListNode next = cur.next;  cur.next = pre;  pre = cur;  cur = next;     }     end.next = pre;     end = begin; } return dummyHead.next;    }}

双向链表

对于链表中的任意节点，既可以通过该节点向后走，也可以通过该节点向前走。

class DoubleNode{    int val;    DoubleNode prev;    //该节点的前一个节点    DoubleNode next;    //后一个节点}

增删改查

点此查看源码