代码随想录打卡Day3|303， 707， 206 链表Part01

学习目标：
● 链表理论基础
● 203.移除链表元素
● 707.设计链表
● 206.反转链表

学习内容：

精髓仍然是双指针，暂时不要求自己掌握递归，递归的使用场景有限制

学习笔记：
1.获取第N个节点的值

对N进行合法判断 N<0 N> size - 1

定义一个临时指针操作，该指针指向头节点

初始化 cur = dummyHead.next

2.头部插入节点

3.尾部插入节点

4.第n个节点前插入节点

5.删除第n个节点

当前操作的永远是cur.next

插入节点的时候，先更新下一条边，再更新上一条边

---

双指针：

1.初始化

prev = null;

cur = head;

2.遍历链表

终止条件：cur指向null

需要一个临时指针，中间变量temp保存cur的下一个节点

学习成果：

203解题过程

707解题过程

// @lc code=start
public 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;
        }
        //声明一个临时变量current 节点
        ListNode curr = head;
        for (int i = 0; i <= index; i++) //链表的遍历需要一节节查找，直到找到当前指针的指向的这一节点
        {
            curr = curr.next;
        }
        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 > size)
        {
            return ;//不合法，无法插入
        }
        //需要直到插入第n个节点的第n-1个节点的指针，才能在两者之间插入

        //更新链表长度
        size++;
        index = Math.Max(0, index);
        //找到前驱节点
        ListNode prev = head;
        for (int i = 0; i< index; i++)
        {
            prev = prev.next;
        }
        //要插入的节点
        ListNode toAddNode = new ListNode(val);
        toAddNode.next = prev.next;
        prev.next = toAddNode;
    }
    
    public void DeleteAtIndex(int index) {
        //合法性判断
        if (index < 0 || index > size)
        {
            return;
        }
        //更新长度
        size--;
        //优先判断，要删除的节点是否是头节点
        if (index == 0)
        {
            head = head.next;//删除头节点
            return; //不必再进行下一步操作
        }
        //找到前驱节点
        ListNode prev = head;
        for (int i = 0 ; i < index; i++)
        {
            prev = prev.next;
        }
        prev.next = prev.next.next;
    }
}
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

206解题过程

public class Solution {
    public ListNode ReverseList(ListNode head) {
        //初始化
        ListNode prev = null;
        ListNode temp = null;
        ListNode curr = head;

        while (curr != null)
        {
            //保存curr的写一个节点
            temp = curr.next;
            //反转prev和curr的方向
            curr.next = prev;
            //移动prev节点
            prev = curr;
            //移动curr接待你
            curr = temp;
        }
        return prev;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21