Kiml's Blog
代码随想录算法训练营第三天-203移除链表元素、707设计链表、206反转链表
Kiml Lv5
  2024-04-24 21:37:00   2024-06-25 15:51:44    1.9k 字  9 分钟  

  • 前言
    状态：链表定义有点不会，基本上是都是看了一半图解后写出来的，而且耗时比较长，可能二刷会好一点吧。

  • 更新

1
2
24.04.24 初始记录
24.05.15 完成题目

初步题解

203 移除链表元素

题目链接：https://leetcode.cn/problems/remove-linked-list-elements/description/

刚开始看到有点懵，习惯了写输入输出，这里不知道怎么输入了。链表这块需要先初始化链表。没有写出来后面是查看了解析。

在具体方法那里，一直尝试只用一个链表做操作，但是运行总是得不到想要的结果。

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
85
public class LE203 {  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        String s = scanner.nextLine();  
        if ("".equals(s.trim())) {  
            System.out.println(new LinkedList());  
            return;  
        }  
        List<Integer> head = Arrays.stream(s.split(",")).map(Integer::parseInt).collect(Collectors.toList());  
        int val = Integer.parseInt(scanner.nextLine());  
  
        // 初始化链表  
        LinkedList linkedList = new LinkedList();  
        for (Integer integer : head) {  
            linkedList.add(integer);  
        }  
  
  
        ListNode listNode = removeElements(linkedList.head, val);  
        System.out.println(listNode);  
    }  

	// 一开始只能写成这个样子
    public static ListNode removeElements(ListNode head, int val) {  
		while (head != null && head.val == val) {  
		    head = head.next;  
		}  
		  
		if (head == null) {  
		    return head;  
		}
    }  
  
    /**  
     * 链表的定义  
     */  
    public static 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 static class LinkedList {  
        private ListNode head;  
  
        public ListNode getHead() {  
            return head;  
        }  
  
        public void setHead(ListNode head) {  
            this.head = head;  
        }  
  
        public ListNode getCurrent() {  
            return current;  
        }  
  
        public void setCurrent(ListNode current) {  
            this.current = current;  
        }  
  
        private ListNode current;  
  
        public void add(int val) {  
            if (head == null) {  
                head = new ListNode(val);  
                current = head;  
            } else {  
                current.next = new ListNode(val);  
                current = current.next;  
            }  
        }  
    }  
}

707 设计链表

题目链接：https://leetcode.cn/problems/design-linked-list/description/

修修改改了很久才通过，要考虑头节点，尾节点。

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
public class LE707 {  
    public static void main(String[] args) {  
        MyLinkedList myLinkedList = new MyLinkedList();  
        myLinkedList.addAtHead(1);  
        myLinkedList.addAtTail(3);  
        // 链表变为 1->2->3        myLinkedList.addAtIndex(1, 2);  
        // 返回 2        myLinkedList.get(1);  
        // 现在，链表变为 1->3        myLinkedList.deleteAtIndex(1);  
        // 返回 3        myLinkedList.get(1);  
    }  
  
    public static class ListNode {  
        private int val;  
        private ListNode next;  
  
        public ListNode() {  
        }  
  
        public ListNode(int val) {  
            this.val = val;  
        }  
    }  
  
    public static class MyLinkedList {  
        private int size;  
        private ListNode head;  
  
        public MyLinkedList() {  
            size = 0;  
            head = new ListNode(0);  
        }  
  
        public int get(int index) {  
            if (index <= -1 || index >= size) {  
                return -1;  
            }  
  
            ListNode indexNode = head;  
            for (int i = 0; i < index; i++) {  
                indexNode = indexNode.next;  
            }  
  
            return indexNode.val;  
        }  
  
        public void addAtHead(int val) {  
            if (size == 0) {  
                size++;  
                head = new ListNode(val);  
                return;  
            }  
            addAtIndex(0, val);  
        }  
  
        public void addAtTail(int val) {  
            addAtIndex(size, val);  
        }  
  
        public void addAtIndex(int index, int val) {  
            if (index > size) {  
                return;  
            }  
  
            if (index < 0) {  
                index = 0;  
            }  
  
            ListNode pre = head;  
            // 找到前一个节点的位置  
            for (int i = 0; i < index - 1; i++) {  
                pre = pre.next;  
            }  
  
            ListNode listNode = new ListNode(val);  
            // 如果插入节点为头节点  
            if (index == 0) {  
                listNode.next = pre;  
                head = listNode;  
                // 长度++  
                size++;  
                return;  
            }  
            // 如果插入位置正好是尾节点 直接前节点指向这个节点 然后return  
            if (index == size) {  
                pre.next = listNode;  
                // 长度++  
                size++;  
                return;  
            }  
  
            // 否则  
            // 先把当前节点的后指针指向前节点的next  
            listNode.next = pre.next;  
            // 再把前节点的后指针指向当前节点  
            pre.next = listNode;  
            // 长度++  
            size++;  
        }  
  
        public void deleteAtIndex(int index) {  
            if (index >= size || index < 0) {  
                return;  
            }  
  
            ListNode pre = head;  
            for (int i = 0; i < index - 1; i++) {  
                pre = pre.next;  
            }  
            // 如果删除节点为头节点  
            if (index == 0) {  
                head = head.next;  
                size--;  
                return;  
            }  
            // 如果删除位置正好是尾节点 直接前节点指向null 然后return  
            if (index + 1 == size) {  
                pre.next = null;  
                // 长度++  
                size--;  
                return;  
            }  
            // 改变当前节点的前节点的后指针，指向下一个节点  
            pre.next = pre.next.next;  
            // 长度--  
            size--;  
        }  
    }  
}

206 反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/description/

偷偷看了下视频图解，按这个思路写的代码：还是比较简单的

image

1
2
3
4
5
6
7
8
9
10
11
12
public static LE707.ListNode reverseList(LE707.ListNode head) {  
    LE707.ListNode pre = null;  
    LE707.ListNode cur = head;  
    while (cur != null) {  
        LE707.ListNode temp = cur.next;  
        cur.next = pre;  
        pre = cur;  
        cur = temp;  
    }  
  
    return pre;  
}

看讲解

203 移除链表元素

题目链接/文章讲解/视频讲解：：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 一开始没有搞懂，前面一个循环是用来干什么的。
// 但是去除前面一步，执行[7,7,7,7] 7 这个用例会多出一个7
public static ListNode removeElements(ListNode head, int val) {  
    while (head != null && head.val == val) {  
        head = head.next;  
    }  
  
    if (head == null) {  
        return head;  
    }  
  
    ListNode pre = head;  
    ListNode cur = head.next;  
    while (cur != null) {  
        if (cur.val == val) {  
            pre.next = cur.next;  
        } else {  
            pre = cur;  
        }  
        cur = cur.next;  
    }  
    return head;  
}

这个题共有三种题解法：

  1. 第一种：添加虚节点。在原先的链表前，添加一个虚拟节点，用于处理可能被删除的头节点。因为删除可能涉及到头节点，所以在方法二中，第一个循环把头节点可能需要删除的情况直接处理掉。

  2. 第二种：不添加虚节点。用一个循环处理可能会被删除的头节点。

  3. 第三种：不加虚节点，同时不添加 pre 节点。加上判断删除节点是否是尾节点。

707 设计链表

题目链接/文章讲解/视频讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

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
//单链表
class ListNode {
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val) {
        this.val=val;
    }
}
class MyLinkedList {
    //size存储链表元素的个数
    int size;
    //虚拟头结点
    ListNode head;

    //初始化链表
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }

    //获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点
    public int get(int index) {
        //如果index非法，返回-1
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode currentNode = head;
        //包含一个虚拟头节点，所以查找第 index+1 个节点
        for (int i = 0; i <= index; i++) {
            currentNode = currentNode.next;
        }
        return currentNode.val;
    }

    //在链表最前面插入一个节点，等价于在第0个元素前添加
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    //在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果 index 大于链表的长度，则返回空
    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        if (index < 0) {
            index = 0;
        }
        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;
    }

    //删除第index个节点
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        size--;
        if (index == 0) {
            head = head.next;
	    return;
        }
        ListNode pred = head;
        for (int i = 0; i < index ; i++) {
            pred = pred.next;
        }
        pred.next = pred.next.next;
    }
}

参考中是直接设置了虚拟头节点解决的，代码会更加简洁。还有一种双向链表的方法，没有仔细研究。

206 反转链表

题目链接/文章讲解/视频讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 递归 
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        // 此时cur为前一个节点，temp为后一个节点。两个节点位置交换，做递归。
        return reverse(cur, temp);
    }
}

按照讲解，一开始写的是双指针方法。

LeetCode 进阶处写了还可以使用递归解决。解法在解析中给出。

代码随想录算法训练营第三天-203移除链表元素、707设计链表、206反转链表
posts/a242ea05/
作者
Kiml
发布于
2024-04-24 21:37
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 初步题解
    1. 203 移除链表元素
    2. 707 设计链表
    3. 206 反转链表
  2. 看讲解
    1. 203 移除链表元素
    2. 707 设计链表
    3. 206 反转链表
© 2022 - 2025    Kiml
由 Hexo 驱动 & 主题 Keep
访客数 访问量
  1. 初步题解
    1. 203 移除链表元素
    2. 707 设计链表
    3. 206 反转链表
  2. 看讲解
    1. 203 移除链表元素
    2. 707 设计链表
    3. 206 反转链表