代码随想录第三天

Posted on Edited on In

链表理论基础

链表是通过指针串联在一起的线性结构。 由data和指针构成

最后一个节点指向null

特殊：
双链表： 由data和两个指针域构成，一个指向下一个节点，一个指向上一个节点
循环链表： 链表收尾相连

存储方式：
在内存中不是连续分布的，是散乱在内存中的

创建链表

这种写法来自kamacoder网上链表基础

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class LinkedList{
	class Node{
		int data;
		Node next;
		
		public Node(int data){
			this.data = data;
			this.next = null;
		}
	
	}
	
	private int length;
	private Node headNode;
	
	public LinkedList(){
		this.length = 0;
		this.headNode = null;
	}
}

代码随想录写法：(ListNode 其实为kamacoder网上Node的写法，但也有区别，这里可以通过constructor构建LinkedList)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class ListNode{
	int data;
	ListNode next;
	
	public ListNode(){
	}
	
	public ListNode(int data){
		this.data = data;
		this.next = null;
	}
	
	public ListNode(int data, ListNode next){
		this.data = data;
		this.next = next;
	}
}

leetcode内置(与代码随想录思路一样）

1
2
3
4
5
6
7
8
9
10
11

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;}
}

链表操作
删除节点： 将该节点的指针跳过下一个节点变成.next;
添加节点：将该节点的指针指到新节点，新节点的下一指针指到原来链表的下一个指针
添加删除操作均为O（1）
但是遍历链表找到对应节点为O（N）

对比数组，数组增删为O（N），遍历为O（1）

203 移除链表元素

https://leetcode.com/problems/remove-linked-list-elements/description/

  1. 直接用原来的链表进行操作
    这种方法处理头结点是特殊操作
    处理方式与虚拟头节点差不多，但是要把头节点先拿出来(注意用while处理)

    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 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;

    }

  2. 使用虚拟头结点进行操作
    可以统一操作
    首先排除空linkedlist
    新建linkNode dummy 连接head，形成虚拟头节点

用for或while loop 遍历寻找元素，设置pre和current指针，如果cur是val，pre的next是cur的next， 如果不是，pre就是cur。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode removeElements(ListNode head, int val){
	if(head == null){
		return head;
	}
	
	ListNode dummy = new ListNode(-1, head);
	
	ListNode pre = dummy;
	ListNode cur = head;
	
	while(cur != null){
		if(cur.val == val){
			pre.next = cur.next;
		} else {
			pre = cur;
		}
		
		cur = cur.next;
	}
	return dummy.next;
}

  1. 不使用虚拟头结点和pre进行操作 (注意判断cur.next的val时使用while)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public ListNode removeELements(ListNode head, int val){
    	while(head != null && head.val == val){
    		head = head.next;
    	}
    	
    	if(head == null){
    		return head;
    	}
    	
    	ListNode cur = head;
    	while(cur != null){
    		while(cur.next != null && cur.next.val == val){
    			cur.next = cur.next.next;
    		}
    		
    		cur = cur.next;
    	}
    	
    	return head;

    }

707 设计链表

https://leetcode.com/problems/design-linked-list/description/

  1. 单链表方法

包括：
在index插入
在index删除
在index查找
在头节点加入
在尾节点加入

在初始化链表时初始一个dummy节点在最前方，

for loop 里面

cur <= index
pre < 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
85
86
87

class ListNode{
	int val;
	ListNode next;
	
	public ListNode(){}
	public ListNode(int val){
		this.val = val;
		this.next = null;
	
	}

}
class MyLinkedList {
	
	int length;
	ListNode head;
    public MyLinkedList() {
        this.length = 0;
		this.head = new ListNode(0);
    }
    
    public int get(int index) {
        if(index < 0||index >= length){
			return -1;
		
		}
		
		ListNode cur = head;
		
		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(length,val);
    }
    
    public void addAtIndex(int index, int val) {
        if (index > length){
			return;
		}
		
		if(index < 0){
			index = 0;
		}
        length++;
		ListNode pre = head;
		
		for(int i = 0; i < index; i++){
			pre = pre.next;
		}
		
		ListNode newNode = new ListNode(val);
		
		newNode.next = pre.next;
		pre.next = newNode;
    }
    
    public void deleteAtIndex(int index) {
		if(index < 0 || index >= length){
			return;
		}	
        length--;
        if(index == 0){
            head = head.next;
            return;
        }
		
		ListNode pre = head;

		for(int i = 0;i < index;i++){
			pre = pre.next;
		}
		
		pre.next = pre.next.next;
    }
}

双链表：

在初始化链表时一定要把头尾的dummy node一起创建，并且连接起来，不然会出现.next null pointer 的错误

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

class ListNode{
    int val;
    ListNode prev,next;

    public ListNode(){}
    public ListNode(int val){
        this.val = val;
    }
}
class MyLinkedList {
    int length;
    ListNode head, tail;

    public MyLinkedList() {
        this.head = new ListNode(0);
        this.tail = new ListNode(0);
        this.length = 0;
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int index) {
        if(index < 0 || index > length - 1){
            return -1;
        }

        ListNode cur = head;

        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(length, val);
    }
    
    public void addAtIndex(int index, int val) {
        if (index > length){
            return;
        }

        if(index < 0){
            index = 0;
        }

        length++;
        ListNode pre = head;

        for(int i = 0; i < index; i++){
            pre = pre.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = pre.next;
        pre.next.prev = newNode;
        newNode.prev = pre;
        pre.next = newNode;
        
        
    }
    
    public void deleteAtIndex(int index) {
        if(index < 0 || index > length - 1){
            return;
        } 

        length--;

        ListNode pre = head;

        for(int i = 0; i < index; i++){
            pre = pre.next;
        }
        System.out.println(index);
        System.out.println(pre.val);
        pre.next.next.prev = pre;
        pre.next = pre.next.next;
        
        
        
    }
}

206 反转链表

https://leetcode.com/problems/reverse-linked-list/description/

1.双指针法

利用temp存储下次的值, 在把prev连接到现在的cur上，在用temp更新cur

相当于把链表下的每一个值一个一个拿出来连接到prev上

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){
		ListNode prev = null;
		ListNode cur = head;
		ListNode temp = null;
		
		
		while (cur != null){
			temp = cur.next;
			cur.next = prev;
			prev = cur;
			cur = temp;
		
		}
		
		return prev;
	
	}
}
  1. 递归法

逻辑和双指针是一样的，也是把next的值存到temp里面，然后反转
递归时，prev就是cur， cur就是temp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution{
	public ListNode reverseList(ListNode head){
		return reverse(null, head);
	}
	
	public ListNode reverse(ListNode prev, ListNode cur){
		if(cur == null){
			return prev;
		}
		
		ListNode temp = cur.next;
		cur.next = prev;
		
		return reverse(cur,temp);
	}	

}

3.从后向前递归 (不太明白，需要再研究)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode reverseList(ListNode head) {
		if(head == null) return null;
		if(head.next == null) return head;
		
		ListNode last = reverseList(head.next);
		
		head.next.next = head;
		head.next = null;
		return last;
    }
}