企业官网建设流程全解析

链表理论基础

链表由一堆结点组成

单链表的结点由数值部分（val）和指向下一个结点的指针部分组成

203.移除链表元素

讲解：

看到题目后第一想法：设置头节点方便操作

看完代码随想录后的想法：递归看不懂

题目总结：

无头节点

/** * Definition for singly-linked list. * 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; } * } */ //自己的 class Solution { public ListNode removeElements(ListNode head, int val) { if(head == null) return head;//处理空节点 ListNode p = head; //处理头节点需要删除的情况 while(p != null && p.val == val){//如果不为空且需要删除 p = p.next; } if(p==null) return p;//如果是因为删完才退出的，就直接返回 //如果不是的话就继续删中间的 head = p; while(p.next != null){//因为之前已经排除了头节点为空的情况，所以直接判断下一个节点是不是空就行 if(p.next.val == val){//如果下一个需要删 p.next = p.next.next; }else{ p = p.next; } } return head; } } class Solution { public ListNode removeElements(ListNode head, int val) { ListNode L = head; while(L != null && L.val == val){//先处理第一个结点需要删除的情况 L = L.next; } ListNode res = L; while(L != null && L.next != null){//再处理之后结点需要删除的情况 if(L.next.val == val){ L.next = L.next.next; }else{ L = L.next; } } return res; } }

有头节点：

class Solution { public ListNode removeElements(ListNode head, int val) { ListNode node = new ListNode(-1); node.next = head; ListNode L = node; while(node != null && node.next != null){ if(node.next.val == val){ node.next = node.next.next; }else{ node = node.next; } } return L.next; } }

递归：

class Solution { public ListNode removeElements(ListNode head, int val) { //终止条件 if(head == null) return head; //递归调用 head.next = removeElements(head.next,val); //本层处理 if(head.val == val){ return head.next; }else{ return head; } } }

707.设计链表

看完代码随想录后的想法：可以使用内部类，原来头节点之后的那个结点的下标为0，需要注意每个方法都要判断下标是否正常。

class MyLinkedList { class ListNode { int val; ListNode next; ListNode(int val) { this.val=val; } } private int size; ListNode head; public MyLinkedList() { size = 0; head = new ListNode(0); } public int get(int index) { if(index < 0 || index >= size) return -1; ListNode cur = head; int i = 0; while(i<=index){ cur = cur.next; i++; } return cur.val; } public void addAtHead(int val) { ListNode newNode = new ListNode(val); newNode.next = head.next; head.next = newNode; size++; } public void addAtTail(int val) { ListNode newNode = new ListNode(val); ListNode cur = head; int i = 0; while(i<size){ cur = cur.next; i++; } cur.next = newNode; size ++; } public void addAtIndex(int index, int val) { if(index > size || index < 0) return; ListNode newNode = new ListNode(val); ListNode cur = head; int i = 0; while(i<index){ cur = cur.next; i++; } newNode.next = cur.next; cur.next = newNode; size++; } public void deleteAtIndex(int index) { if(index >= size || index < 0) return; ListNode cur = head; int i = 0; while(i<index){ cur = cur.next; i++; } cur.next = cur.next.next; size--; } }

206.反转链表

先自己做的时候：使用了3个指针，分别指向当前结点前，当前结点，当前结点后，然后慢慢翻转；

看完代码随想录后：递归法比较难

/** * Definition for singly-linked list. * 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; } * } */ //我自己写的双指针 class Solution { public ListNode reverseList(ListNode head) { ListNode pre,cur,nex; if(head == null || head.next == null) return head; pre = null; cur = head;//注意：要从第一个节点开始，不要直接从第二个节点开始，这样的话第一个节点的next还是有值，链表就有循环了，就会报错 while(cur != null){ nex = cur.next;//保存了下一个的位置 cur.next = pre; pre = cur; cur = nex; } return pre; } } //递归法 class Solution { public ListNode reverseList(ListNode head) { //终止条件,同时也能判断空链表和单节点链表 if(head == null || head.next == null) return head; //递归调用 ListNode pre = reverseList(head.next);//这里返回的不是后面链表的尾，而是后面链表的头部，因为最终要返回头部 //本层处理 head.next.next = head;//可以通过head.next访问到后面链表的尾部，然后将当前节点接到尾部的下一个 head.next = null;//然后给当前节点制空，以免尾部成环 return pre; } }

鉴于作者水平有限，文章可能存在错误

如有指正，十分感谢