​
​

活动地址：CSDN21天学习挑战赛

链表

**

1，定义

什么是链表？

数组（Array）是一种线性表数据结构。它用指针，将一组零散的内存块串联起来。

线性表：线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。

2，常见的链表结构

因为指针的指向五花八门，所以链表结构各种各样，三种最常见的链表结构：单链表，双向链表，循环链表

单链表

双向链表

循环链表

3，与数组的对比

数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。
链表支持插入删除，时间复杂度为O(1)。

4，插入

改变指针的指向，so easy

5，删除

改变指针的指向，so easy

6，查找

从头结点，一个一个的找

…

7，代码练习

设计链表

设计链表

 public class ListNode{
        int val;
        ListNode next;
        ListNode(int x){
            val=x;
        }
        public String toString(){
            return ""+val;
        }
}
class MyLinkedList {
    int size;
    ListNode head;
    public MyLinkedList() {
        size=0;
        head= new ListNode(0);
    }
    
    public int get(int index) {
        if(index<0 || index>=size){
            return -1;
        }
        ListNode curr=head;
        for(int i=0;i<index+1;i++){
            curr=curr.next; 
            //System.out.println(curr);

        } 
        
        return curr.val;

    }
    
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    
    public void addAtIndex(int index, int val) {
        
        if(index<0) index=0;
        if(index>size) return;
        ++size;
        
        ListNode pred=head;
        for(int i=0;i<index;i++) pred=pred.next;

        ListNode toAdd = new ListNode(val);

        toAdd.next=pred.next;
        pred.next=toAdd;
        
        
    }
    
    public void deleteAtIndex(int index) {
        System.out.printf("%d %d\n",index,size);
        if(index<0||index>=size) return;
        size--;

        ListNode pred=head;
        for(int i=0;i<index;i++) pred=pred.next;
        //System.out.println(pred);
        pred.next=pred.next.next;
        //System.out.println(pred.next);


    }
}

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


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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

螺旋矩阵 IV

2326. 螺旋矩阵 IV

/**
 * 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 {
    int [][] dir = {
        {0,1},
        {1,0},
        {0,-1},
        {-1,0}
    };
    public int[][] spiralMatrix(int m, int n, ListNode head) {
        int[][] matrix = new int[m][n];
        int i,j=0,x=0,y=-1;
        for(i=0;i<m;i++){
            Arrays.fill(matrix[i],-1);
        }
        ListNode cur =head;
        int[] loc = dir[0];
        while(cur!=null){
            int newx=x+loc[0];
            int newy=y+loc[1];
            
            
            
            

            if(newx>=m || newy>=n || newx<0 || newy<0 || matrix[newx][newy]!=-1){
                j++;
                loc= dir[j%4];
            }
            x+=loc[0];
            y+=loc[1];
            matrix[x][y]=cur.val;
            cur=cur.next;
            
            
            
            
        }
        return matrix;
        


    }
}

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

奇偶链表

328. 奇偶链表

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode evenHead = head.next;
        ListNode odd = head, even = evenHead;

        while(even !=null && even.next != null){
            odd.next=even.next;
            odd = odd.next;
            even.next=odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

分隔链表

725. 分隔链表

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        // 扫描链表，得到总长度 cnt
        int cnt = 0;
        ListNode tmp = head;
        while (tmp != null && ++cnt > 0) tmp = tmp.next;
        // 理论最小分割长度
        int per = cnt / k;
        // 将链表分割为 k 份（sum 代表已经被处理的链表长度为多少）
        ListNode[] ans = new ListNode[k];
        for (int i = 0, sum = 1; i < k; i++, sum++) {
            ans[i] = head;
            tmp = ans[i];
            // 每次首先分配 per 的长度
            int u = per;
            while (u-- > 1 && ++sum > 0) tmp = tmp.next;
            // 当「已处理的链表长度 + 剩余待分配份数 * per < cnt」，再分配一个单位长度
            int remain = k - i - 1;
            if (per != 0 && sum + per * remain < cnt && ++sum > 0) tmp = tmp.next;
            head = tmp != null ? tmp.next : null;
            if (tmp != null) tmp.next = null; 
        }
        return ans;
    }
}

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

链表组件

817. 链表组件

class Solution {
    public int numComponents(ListNode head, int[] G) {
        Set<Integer> Gset = new HashSet();
        for (int x: G) Gset.add(x);

        ListNode cur = head;
        int ans = 0;

        while (cur != null) {
            if (Gset.contains(cur.val) &&
                    (cur.next == null || !Gset.contains(cur.next.val)))
                ans++;
            cur = cur.next;
        }

        return ans;
    }
}



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

设计循环队列

622. 设计循环队列

class Node {
  public int value;
  public Node nextNode;

  public Node(int value) {
    this.value = value;
    this.nextNode = null;
  }
}

class MyCircularQueue {

  private Node head, tail;
  private int count;
  private int capacity;

  /** Initialize your data structure here. Set the size of the queue to be k. */
  public MyCircularQueue(int k) {
    this.capacity = k;
  }

  /** Insert an element into the circular queue. Return true if the operation is successful. */
  public boolean enQueue(int value) {
    if (this.count == this.capacity)
      return false;

    Node newNode = new Node(value);
    if (this.count == 0) {
      head = tail = newNode;
    } else {
      tail.nextNode = newNode;
      tail = newNode;
    }
    this.count += 1;
    return true;
  }

  /** Delete an element from the circular queue. Return true if the operation is successful. */
  public boolean deQueue() {
    if (this.count == 0)
      return false;
    this.head = this.head.nextNode;
    this.count -= 1;
    return true;
  }

  /** Get the front item from the queue. */
  public int Front() {
    if (this.count == 0)
      return -1;
    else
      return this.head.value;
  }

  /** Get the last item from the queue. */
  public int Rear() {
    if (this.count == 0)
      return -1;
    else
      return this.tail.value;
  }

  /** Checks whether the circular queue is empty or not. */
  public boolean isEmpty() {
    return (this.count == 0);
  }

  /** Checks whether the circular queue is full or not. */
  public boolean isFull() {
    return (this.count == this.capacity);
  }
}


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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74