day3 | 203.移除链表元素、707.设计链表、206.反转链表

题目链接：203. 移除链表元素 - 力扣（LeetCode）

题目描述：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 

解题思路：

• 方法一：（不带虚拟头结点：要考虑删除的结点为头结点的情况）

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

• 方法二：（带虚拟头结点，不用考虑删除的节点为头结点的情况）

 1 class Solution {
 2     public ListNode removeElements(ListNode head, int val) {
 3         //带头结点和pre
 4         if(head==null) return head;
 5         ListNode p = head;
 6         ListNode dummy = new ListNode(-1,head);
 7         ListNode pre = dummy;
 8         while(p!=null){
 9             if(p.val==val){
10                 pre.next=p.next;
11             }
12             else pre=p; //若p结点的值不等于val，p的前驱节点pre跟p往后走
13             p=p.next;
14         }
15         return dummy.next;  
16     }
17 }

题目链接：707. 设计链表 - 力扣（LeetCode）

题目描述：设计链表

解题思路：

 1 class ListNode{//定义单链表的结构体
 2     int val;
 3     ListNode next;
 4     ListNode(){};
 5     ListNode(int val){
 6         this.val=val;
 7     }
 8 }
 9 class MyLinkedList {
10     int size;//单链表中元素的个数
11     ListNode head;//虚拟头结点
12     public MyLinkedList() {//初始化单链表
13         size=0;
14         head = new ListNode(0);//初始化虚拟头结点且值为null
15     }
16     
17     public int get(int index) {//获取链表中的元素，index从0开始
18         //如果index非法则返回-1
19         if(index<0 || index >= size) return -1;
20         ListNode p = head;
21         for(int i=0; i<=index ;i++){
22             p=p.next;
23         }
24         return p.val;
25     }
26     
27     public void addAtHead(int val) {//头插法
28         ListNode q = new ListNode(val);
29         q.next=head.next;
30         head.next=q;
31         size++;
32     }
33     
34     public void addAtTail(int val) {//尾插法
35         addAtIndex(size,val);
36     }
37     
38     public void addAtIndex(int index, int val) {
39         //若index大于链表长度，不会插入结点；
40         if(index > size) return ;
41         //若index小于0，使用头插法
42         if(index < 0 ){
43             addAtHead(val);
44             size++;
45         }
46         //若index大于0小于链表长度
47         ListNode s = new ListNode(val);
48         ListNode p = head;
49         for(int i=0;i<index;i++){
50             p=p.next;
51         }
52         s.next=p.next;
53         p.next=s;
54         size++;
55         
56     }
57     
58     public void deleteAtIndex(int index) {
59         if(index<0 || index >= size)return ;
60         ListNode p=head;
61         size--;
62         if(index==0){
63             head=head.next;
64             return;
65         }
66         for(int i = 0;i<index;i++){
67             p=p.next;
68         }
69         p.next=p.next.next;//p指向被删除结点的前驱结点  
70     }
71 }

注意：

• 指针p最好从head开始，否则可能会出现很多空指针错误，在对单链表进行插入操作时，尽量避免出现 p.next.next 的语句，这样很容易出现空指针错误。
• 头插法 addAtHead 和尾插法 addAtTail 可以用函数 addAtIndex 完成，这样可以节约很多时间。

双链表：详见文章代码随想录 (programmercarl.com)

题目链接：206. 反转链表 - 力扣（LeetCode）

题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解题思路：

• 方法一：双指针法

　　定义三个指针 curr、pre、temp

　　curr：指向当前需要反转的结点；

　　pre：初始化为null，作为curr的前驱结点；

　　temp：暂时保存 curr.next 结点；

 1 class Solution {
 2     public ListNode reverseList(ListNode head) {
 3         ListNode curr = head;
 4         ListNode pre = null;
 5         ListNode temp;
 6         while(curr!=null){  //java语言中，while条件直接写curr会报错，必须写成curr!=0的形式
 7             temp=curr.next;
 8             curr.next=pre;
 9             pre=curr;
10             curr=temp;
11         }
12     return pre;
13     }
14 }

• 方法二：递归法

 1 class Solution {
 2     public ListNode reverseList(ListNode head) {
 3        return reverse(null,head);
 4     }
 5     private ListNode reverse(ListNode pre,ListNode curr){
 6         if(curr==null) return pre; //递归出口
 7         ListNode temp=curr.next;
 8         curr.next=pre;
 9         return reverse(curr,temp);
10     }
11 }