【代码随想录】day03 203.移除链表元素 707.设计链表 206.反转链表_707超出内存限制

移除链表元素

leetcode: 203.移除链表元素.

拿到题目的思考

首先得清楚java内部的链表结构的实现。leetcode给我们提供了一个可以使用的简单模型：

  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; }
 }
1
2
3
4
5
6
7

移除链表元素，本质上就是将当前元素的前一个元素的指针指向它的下一个元素。如果移除的元素是链表的第一个元素，就使用第二个元素作为第一个元素。

观看教程后的思考

因为第一个元素的特殊性，所以会考虑可不可以对整个流程进行统一处理，所以会产生两种解法：
1.生成一个虚拟的头结点，它的存在就是为了让第一个头结点移除逻辑和其他节点相同。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
		ListNode moakPre = new ListNode(-1,head);
		ListNode cur = moakPre;
		while (cur!=null){
			if (cur.next!=null&&cur.next.val==val){
				cur.next=cur.next.next;
			}else{
				cur = cur.next;
			}
		}
		return moakPre.next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.分开处理两套逻辑

class Solution {
    public ListNode removeElements(ListNode head, int val) {
		while (head!=null&&val== head.val){
			head=head.next;
		}
		ListNode curr = head;
		while(curr!=null){
			while (curr.next!=null&&curr.next.val==val){
				curr.next = curr.next.next;
			}
			curr = curr.next;
		}
		return head;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

因为java并没有指针，我们使用引用切换当前迭代的节点信息。需要注意判断的时机和切换的点。

设计链表

leetcode: 707. 设计链表.

拿到题目的思考

首先按照如下方式进行了设计：

class MyLinkedList {

    public Node node;

    private class Node {
        public int val;
        public Node next;

        public Node() {
        }

        public Node(int val, Node next) {
            this.val  = val;
            this.next = next;
        }
    }

    public MyLinkedList() {
        node = new Node(-1,null);
    }

    public int get(int index) {
        int curIndex = 1;
        int result = -1;
        Node cur = node;
        while (cur != null) {
            if (curIndex++ == index) {
                result = cur.val;
            }
            cur = cur.next;
        }
        return result;
    }

    public void addAtHead(int val) {
        node = new Node(val, node);
    }

    public void addAtTail(int val) {
        Node cur = node;
        while (cur != null) {
            if (cur.next == null) {
                Node tail = new Node(val, null);
                cur.next = tail;
            }
            cur = cur.next;
        }
    }

    public void addAtIndex(int index, int val) {
        if (index == 1) {
            addAtHead(val);
        }
        Node cur = node;
        int curIndex = 2;
        while (cur != null) {
            if (curIndex == index) {
                Node tail = new Node(val, cur.next.next);
                cur.next = tail;
            }
            cur = cur.next;
        }
    }

    public void deleteAtIndex(int index) {
        if (index == 1) {
            node = node.next;
        }
        Node cur = node;
        int curIndex = 2;
        while (cur != null) {
            if (curIndex == index) {
                cur.next = cur.next.next;
            }
            cur = cur.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

结果测试时显示超出内存限制了。个人感觉是循环判断的节点出了问题。反复查证后并未发现比较好的方法解决这个问题。索性引入size来进行循环判断，抛弃while。
修改后的方式：

class MyLinkedList {

        public Node head;
        public int size;

        private class Node {
            public int val;
            public Node next;

            public Node() {
            }

            public Node(int val) {
                this.val = val;
            }
        }

        public MyLinkedList() {
            size = 0;
            head = new Node(0);
        }

        public int get(int index) {
            if (index < 0 || index > size - 1) {
                return -1;
            }
            Node cur = head.next;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            return cur.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;
            }
            Node cur = head;
            Node newNode = new Node(val);
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }

            newNode.next = cur.next;
            cur.next = newNode;
            size++;

        }

        public void deleteAtIndex(int index) {
            if (index < 0 || index >= size) {
                return;
            }
            Node cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
            size--;
        }
    }
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

看完教程的思考

题目中有一个很容易产生歧义的地方：第几个元素，居然会出现第0个。

反转链表

leetcode: 206.反转链表 .

拿到题目的思考

一开始写的时候发生了回环问题。因为链表和数组不同，链表上存储的全都是引用（指针），所以简单的反转会将后续的长链都引用过来，所以需要一个新的空节点对原来的值进行存储，思考以后代码如下：

class Solution {
    public ListNode reverseList(ListNode head) {
		if(head==null){
			return head;
		}
		ListNode temp = new ListNode(head.val,null);
		ListNode cur = head.next;
		while (cur!=null){
			ListNode preTemp = new ListNode(cur.val,temp);
			temp = preTemp;
			cur = cur.next;
		}
		return temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

观看教程后的思考

我上面写的代码其实是变种的双指针，使用temp保存后一个节点指针，用preTemp保存前一个节点指针。也可以使用递归法解决该问题：

class Solution {
    public ListNode reverseList(ListNode head) {
		return reverse(null,head);
    }

	private ListNode reverse(ListNode pre,ListNode cur){
		if(cur==null){
			return pre;
		}
		ListNode temp = null;
		temp = cur.next;
		cur.next = pre;
		return reverse(cur,temp);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15