赞
踩
今天开始搞链表的题目,因为用的Java,先看了下力扣提供的链表:
- /**
- * 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) {
- while (head != null && head.val == val) {
- head = head.next;
- }
- if (head == null) return head;
-
- ListNode p = head;
- while (p != null) {
- if (p.next != null && p.next.val == val) {
- p.next = p.next.next;
- } else {
- p = p.next;
- }
-
- }
- return head;
- }
- }

看了网上经常说的哨兵节点,加入后就可以消除头节点的特殊性
- class Solution {
- public ListNode removeElements(ListNode head, int val) {
- if (head == null) return head;
-
- ListNode dummy = new ListNode(-1,head);
- ListNode p = dummy;
- while(p != null) {
- if (p.next != null && p.next.val == val) p.next = p.next.next;
- else p = p.next;
- }
- return dummy.next;
- }
- }
不用解释,直接手搓就行
- class MyLinkedList {
- int size;
- ListNode head;
- public MyLinkedList() {
- size = 0;
- head = new ListNode(0);
- }
-
- public int get(int index) {
- if (index >= size || index < 0) return -1;
- ListNode p = head;
- while(p.next != null && index-- >= 0) {
- p = p.next;
- }
- return p.val;
- }
-
- public void addAtHead(int val) {
- ListNode node = new ListNode(val, head.next);
- head.next = node;
- size++;
- }
-
- public void addAtTail(int val) {
- ListNode p = head;
- while(p.next != null && size-- > 0) {
- p = p.next;
- }
- ListNode node = new ListNode(val);
- p.next = node;
- size++;
- }
-
- public void addAtIndex(int index, int val) {
- if (index > size) {
- return;
- }
- if (index < 0) {
- index = 0;
- }
- ListNode p = head;
- while(p.next != null && index-- >= 0) {
- p = p.next;
- }
- ListNode node = new ListNode(val,p.next);
- p.next = node;
- size++;
- }
-
- public void deleteAtIndex(int index) {
- if (index < 0 || index >= size) {
- return;
- }
- ListNode p = head;
- while(p.next != null && index-- >= 0) {
- p = p.next;
- }
- p.next = p.next.next;
- size--;
- }
- }

老题了,重点在于反向后链表会断裂,所以必须提前保存原来的下一个才能继续遍历
- class Solution {
- public ListNode reverseList(ListNode head) {
- //本质上就是箭头的转换
- ListNode cur = head, pre = null, temp = null;
- while (cur != null) {
- temp = cur.next;
- cur.next = pre;
- pre = cur;
- cur = temp;
- }
- return pre;
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。