福州++网站建设,管家婆免费仓库管理软件,模板之家会员,fullpage wow做的网站链表 简介[简单] 203. 移除链表元素[中等] 707. 设计链表[简单] 206. 反转链表[简单] 24. 两两交换链表中的节点[简单] 19. 删除链表的倒数第 N 个结点 简介
记录一下自己刷题的历程以及代码。写题过程中参考了 代码随想录。会附上一些个人的思路#xff0c;如果有错误#… 链表 简介[简单] 203. 移除链表元素[中等] 707. 设计链表[简单] 206. 反转链表[简单] 24. 两两交换链表中的节点[简单] 19. 删除链表的倒数第 N 个结点 简介
记录一下自己刷题的历程以及代码。写题过程中参考了 代码随想录。会附上一些个人的思路如果有错误可以在评论区提醒一下。
[简单] 203. 移除链表元素
原题链接 一前一后两个指针做遍历操作记得 开头对空链表做判断结尾对head是否需要删除做判断
class Solution {public ListNode removeElements(ListNode head, int val) {if (head null) {return head;}ListNode before head; // 标记删除元素前一个元素ListNode del head.next; // 标记删除元素while(del ! null){// 删除if(del.val val) {before.next del.next;del before.next;}else{// 前进before del;del del.next;}}if(head.val val) return head.next;return head;}
}[中等] 707. 设计链表
原题链接 根据平时写Java工程的习惯加入了length属性记录链表长度方便做过界判断。 链表设计上默认有一个虚的头结点不计算长度方便做插入和删除操作。
class MyLinkedList {//考虑存在虚的头结点MyLinkedList next;int val;//维护一个私有变量length表示长度//方便查找时做越界判断private int length;public MyLinkedList() {}public int get(int index) {if(index length - 1) return -1;int count index;MyLinkedList pointer this.next;while(count ! 0){pointer pointer.next;count--;}return pointer.val;}public void addAtHead(int val) {MyLinkedList newHead new MyLinkedList();newHead.val val;newHead.next this.next;this.next newHead;length;}public void addAtTail(int val) {MyLinkedList newTail new MyLinkedList();newTail.val val;MyLinkedList pointer this;while(pointer.next ! null) pointer pointer.next;pointer.next newTail;length;}public void addAtIndex(int index, int val) {if(index length) return;else if(index 0){addAtHead(val);return;}else if(index length) {addAtTail(val);return;}//以上情况之外插入的位置都会有前置节点int count index;MyLinkedList pointer this.next;while(count 1){pointer pointer.next;count--;}MyLinkedList newNode new MyLinkedList();newNode.val val;newNode.next pointer.next;pointer.next newNode;length;}public void deleteAtIndex(int index) {//头跟尾分开考虑if(index length - 1) return;int count index;MyLinkedList pointer this;while(count 0){pointer pointer.next;count--;}if(pointer.next ! null){pointer.next pointer.next.next;}length--;}public void printList(){System.out.print([);System.out.print(val);MyLinkedList pointer this.next;while(pointer ! null){System.out.print(, pointer.val);pointer pointer.next;}System.out.print(]);System.out.print( length: length);System.out.print(\n);}
}public class main {public static void main(String[] args) {MyLinkedList myLinkedList new MyLinkedList();myLinkedList.printList();myLinkedList.addAtHead(1);myLinkedList.printList();myLinkedList.addAtTail(3);myLinkedList.printList();myLinkedList.addAtIndex(1, 2);myLinkedList.printList();System.out.println(myLinkedList.get(1));myLinkedList.deleteAtIndex(0);myLinkedList.printList();System.out.println(myLinkedList.get(0));}
}[简单] 206. 反转链表
原题链接
直接在原链表上挨个改变next指针指向做原地倒置。注意边界情况的判断即可
class Solution {public ListNode reverseList(ListNode head) {if(head null) return head;ListNode pre null;ListNode cur head;ListNode temp head.next;while(cur ! pre){cur.next pre;pre cur;if(temp ! null) {cur temp;temp cur.next;}}return cur;}
}在有虚头结点的情况下可以做头插法反转同理这题也可以自己给出一个虚头结点使用头插法反转链表。
class Solution {public ListNode reverseList(ListNode head) {ListNode vHead new ListNode();vHead.next null;ListNode cur head;while(cur ! null){ListNode temp cur.next;cur.next vHead.next;vHead.next cur;cur temp;}return vHead.next;}
}[简单] 24. 两两交换链表中的节点
原题链接
定义一个虚的头结点方便后续循环操作因为转换两个节点不只是这两个节点的next需要做处理两个节点的上一个节点的next也需要重新改变指向缺少虚头结点的情况下每次在head上做转换操作的时候不需要操作前置节点其他情况都需要就无法统一操作。
class Solution {public ListNode swapPairs(ListNode head) {if (head null || head.next null) return head; //长度为0或1直接返回ListNode vHead new ListNode();vHead.next head; //设定虚头结点ListNode pre vHead;ListNode cur head;while(cur ! null cur.next ! null){pre.next cur.next;cur.next pre.next.next;pre.next.next cur;pre cur;cur cur.next;}return vHead.next;}
}[简单] 19. 删除链表的倒数第 N 个结点
原题链接
删除一个节点需要找到他的前置节点同样设置虚头结点方便操作没有虚头结点就是多一个对删除第一个元素的判断因为除了第一个元素之外其他元素都有前置节点需要改变next指针。使用快慢指针的思路让前一个指针先走n步之后两个指针一起前进第二个指针就会比第一个指针慢n步就能指向我们需要删除的节点。
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode vHead new ListNode();vHead.next head;ListNode node vHead;ListNode delete vHead;while(n-- ! 0){node node.next;}while(node.next ! null){node node.next;delete delete.next;}delete.next delete.next.next;return vHead.next;}
}
