链表：

基本操作

线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因比随机存取元素时比较简单，但是这个特点也使得在插入和删除元素时，造成大量的数据元素移动，同时如果使用静态分配存储单元，还要预先占用连续的存储空间，可能造成空间的浪费或空间的溢出。如果采用链式存储，就不要求逻辑上相邻的数据元素在物理位置上也相邻，因此它没有顺序存储结构所具有的缺点，但同时也失去了可随机存取的优点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private Node head;
private int N;

//    节点类
private class Node {
    T item;
    Node next;

    //       成员类，定义每个节点
    public Node(T item, Node next) {
        this.item = item;
        this.next = next;
    }
}

初始化头结点：

1
2
3
4
5
6
7
8
    //    构造方法
    public LinkList() {
//        初始化链表
        this.head = new Node(null, null);
//        初始化链表的长度
        this.N = 0;
    }

获取指定元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    public T get(int i) {
//        判断非正常的元素
        if (i > N || i < 0) {
            throw new IllegalArgumentException("index is error");
        } else {
            int k = 0;
//            从头结点开始进行遍历
            Node node = head;
//            找到指定位置的前一个元素
            while (k < i && node != null) {
                node = node.next;
                k++;
            }
//            获取指定位置的元素的下一个元素
            Node crrNode = node.next;
            return crrNode.item;
        }
    }

尾插法：

该方法从一个空表开始依次读取数组a中的元素,生成一个新结点s,将读取的数组元素存放到该结点的数据域中,然后将建插人到当前链表的表尾上,如图2.18所示,直到数组a的所有元素读完为止。为此需要增加一个尾指针r,使其始终指向当前链表的尾结点,每插人一个新结点后让:指向这个新结点最后还需要将r所指结点(尾结点)的next域置为空。采用尾插法建表的算法如下:

r->next =s

r=s

image-20220301213649951

删除一个结点：

image-20220301213412117

q=p->next;//q临时保存被删除的结点

p->next=q->next //从链表删除结点q

或者

p->next =p->next->next 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    public T remove(int n) {
//        删除指定位置的节点
        if (n < 0 || n > N) {
            throw new IllegalArgumentException("index error");
        } else {
            Node pre = head;
//            找到指定的前一个结点
            for (int i = 0; i < n - 1; i++) {
                pre = pre.next;
            }
//            保存要删除的结点
            Node deleNode = pre.next;
//             要删除节点的下一个
            pre.next = deleNode.next;
            N--;
            return deleNode.item;
        }
    }

插入结点

这里插人指在单链表的两个数据域分别为α和b的结点(已知a结点的指针p)之间插人一个数据域为α的结点(由s指向它).加图2.14(a)所示。其操作是首先让x结点的指针域(s一>next)指向(b结点( p一>next) 然后a结点的指针域O（p一> next)指向x结点（s）,从而实现3个结点之间逻辑兰系的亦化.插从特程如图2.14(b)和(c)所示,图2.14(d)是插入后的结果。

​ s->next=p->next

​ p->next =s

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
    //    指定位置插入元素
    public void insert(T t, int n) {
        if (n < 0) {
            throw new IllegalArgumentException("index is error");
        } else {
//            先找到指定位置的前一个元素
            Node pre = head;
            for (int i = 0; i < n - 1; i++) {
                pre = pre.next;
            }
//            指向原来位置上的结点，初始化下一个位置的指向的节点
            Node indexNode = new Node(t, pre);
//           改变前一个引用地址值
            pre.next = indexNode;
//            元素个数+1
            N++;
        }
    }

    //    插入一个元素
    public void insert(T t) {
        Node node = head;
        while (node.next != null) {
            node = node.next;
        }
        Node newNode = new Node(t, null);
        node.next = newNode;
//        元素个数
        N++;
    }

快慢指针解决环路：

给定一个链表，判断链表中是否有环。

问题分析

如果没有环，快指针将停在链表的末尾

如果有环，那么最后就会相遇

快慢指针速度问题

  1. 每次移动慢指针一步，而移动快指针移动两步

image-20220305160116120

​

方法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        if (head == null) {
            return false;
        }
//        快指针的前两步数据都不能够为空值
        while (fast.next != null && fast.next.next != null) {
//            快指针前进两步
            fast = fast.next.next;
//            慢指针前进一步
            slow = slow.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

假如有环，那么快慢指针最终都会走到环上，假如环的长度是m，快慢指针最近的间距是n，如下图中所示

快指针每次走两步，慢指针每次走一步，所以每走一次快慢指针的间距就要缩小一步，在图一中当走n次的时候就会相遇，在图二中当走m-n次的时候就会相遇。

image.png

复杂度分析

时间复杂度：

O(N），其中 N是链表中的节点数。

  • 当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。
  • 当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N轮。

空间复杂度：

O(1) 我们只使用了两个指针的额外空间。

方法二：

存放至set集合中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
   * @description: 判断圈中是否有环，利用set集合的特性
   * @param:
   * @return:
   * @date: 2022/3/5 16:18
   */
   public boolean hasCycleBySet(ListNode head) {
       if (head == null) {
           return false;
       }
       ListNode pre = head;
       Set<ListNode> isCycle = new HashSet<>();
       while (pre.next != null) {
           pre= pre.next;
           if (!isCycle.add(pre)) {
               return true;
           }
       }
       return false;
   }

时间复杂度：O(N)，其中 N是链表中的节点数。最坏情况下我们需要遍历每个节点一次。

空间复杂度：O(N)，其中 N 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。

环形链表 II

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

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

不允许修改 链表。

image-20220305172722786

image-20220305172731325

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//  使用set集合进行判断返回的结点值
//    时间与空间复杂度均为 O(n)
    public ListNode detectCycle(ListNode head) {
        if (head==null){
            return  null;
        }
//        当函数只有一个数值时
        if (head!=null&&head.next==null){
            return  null;
        }
        ListNode pre =head;
        Set<ListNode> list= new HashSet<>();
//[1,2]
        while (pre!=null&&pre.next!=null){
//
            if (!list.add(pre)){
                return pre;
            }
//            不能将加入放在前面,会导致1,2判断不出，1并没有放在数组中
            pre =pre.next;

        }
        return  null;
    }

160. 相交链表 - 力扣（LeetCode）

Hash 表方法：

先将链表 A 放入 Map 中，然后依次取出判断是否含有该值，如果第一个有的话就是代表有该值为链表相交结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
    ListNode first = headA;
    ListNode second = headB;
    HashMap<ListNode,ListNode> map = new HashMap<>();
    if (headA==null ||headA==null){
        return null;
    }

     while (first!=null){
         map.put(first,first);
        first= first.next;
     }
     while (second!=null){
         if (map.get(second)!=null){
             return second;
         }
      second =second.next;
     }

    return null;

    }
}

image-20220909184536200

方法二（双指针法）：

微信图片_20200419110414.png

一种比较巧妙的方式是，分别为链表 A 和链表 B 设置指针 A 和指针 B，然后开始遍历链表，如果遍历完当前链表，则将指针指向另外一个链表的头部继续遍历，直至两个指针相遇。
最终两个指针分别走过的路径为：
指针 A :a+c+b
指针 B :b+c+a
明显 a+c+b = b+c+a, 因而如果两个链表相交，则指针 A 和指针 B 必定在相交结点相遇。

  • 时间复杂度为 o (m+n), 其中 m 和 n 分别为两个指针的长度，
  • 空间复杂度为 o (1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

    public ListNode getIntersectionNode02(ListNode headA, ListNode headB) {

    if (headA==null||headB==null){
        return  null;
    }
    ListNode pA = headA;
    ListNode pB = headB;
//    如果pA走完,就直接走pB了
    while (pA!=pB){
        if(pA==null){
            pA=headB;
        }else {
            pA=pA.next;
        }
        if(pB==null){
            pB=headA;
        }else {
            pB=pB.next;
        }
    }
//    返回首结点的值
    return pA;
    }

合并两个有序链表

image-20220909201412790

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//         利用哑结点防止头指针是空值
       ListNode dummy = new ListNode(-1);
       ListNode p = dummy;
       ListNode pA = list1;
       ListNode pB = list2;
//         遍历到都等于空值时，停止遍历
     while(pA!=null&&pB!=null){
          
         if(pA.val>pB.val){
             p.next= pB;
             pB= pB.next;
         }else{
            p.next=pA;
            pA=pA.next;
         }
//          指针需要往前移动
         p=p.next;
         
     }
              if (pA != null) {
            p.next = pA;
        }

        if (pB!= null) {
            p.next = pB;
        }

      return  dummy.next;  
    }
}

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

递归魔法：反转单链表 :: labuladong 的算法小抄 (gitee.io)

头插法

image-20220909230027349

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public ListNode reverseList(ListNode head) {
   //使用头插法保证头部元素不变化
        ListNode dummy = new ListNode(0);
        ListNode temp ;
        ListNode pre;
        if(head==null){
            return head;
        }
        while(head!=null){
            temp = new ListNode(head.val,head);
//            记录哑结点的下一个
            pre = dummy.next;
//         哑结点的下一个等于新增的结点
            dummy.next = temp;
//         新增结点的下一个等于哑结点的下一个
            temp.next= pre;
//           链表继续往下走
            head = head.next;
        }
        return dummy.next;
    }
}

使用递归进行反转

1
2
3
4
5
6
7
8
9
10
11

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}

reverse(head.next) 执行完成后，整个链表就成了这样：

image-20220928134837830

并且根据函数定义，reverse 函数会返回反转之后的头结点，我们用变量 last 接收了。

1
2

head.next.next = head;

image-20220928134906765

1
2
3

head.next = null;
return last;

image-20220928134924886

1
2
3
4

if (head == null || head.next == null) {
    return head;
}

意思是如果链表为空或者只有一个节点的时候，反转结果就是它自己，直接返回即可。

2、当链表递归反转之后，新的头结点是 last，而之前的 head 变成了最后一个节点，别忘了链表的末尾要指向 null：

head.next = null;