链表概念
移除链表元素
体会虚拟头结点的便利
/** @lc app=leetcode.cn id=203 lang=java** [203] 移除链表元素*/// @lc code=start
/*** 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) {ListNode a = new ListNode(-1, head);ListNode b = a;while (b.next != null && b != null) {if (b.next.val == val) {b.next = b.next.next;} else {b = b.next;}}return a.next;}
}
// @lc code=end设计链表
理解链表的基本操作，注意边界值问题，理清思路
/** @lc app=leetcode.cn id=707 lang=java** [707] 设计链表*/// @lc code=start
class MyLinkedList {class ListNode {int val;ListNode next;ListNode(int val) { this.val = val; }}private ListNode head; // 头节点private int length;public MyLinkedList() {head = null;length = 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) {ListNode newNode = new ListNode(val);newNode.next = head;head = newNode;length++;}public void addAtTail(int val) {if (head == null) {addAtHead(val);return;}ListNode cur = head;while (cur.next != null) cur = cur.next;cur.next = new ListNode(val);length++;}public void addAtIndex(int index, int val) {if (index > length) return;if (index == 0) {addAtHead(val);return;}// 找到 index 的前一个节点ListNode prev = head;for (int i = 0; i < index - 1; i++) prev = prev.next;ListNode newNode = new ListNode(val);newNode.next = prev.next;prev.next = newNode;length++;}public void deleteAtIndex(int index) {if (index < 0 || index >= length) return;if (index == 0) {head = head.next;} else {ListNode prev = head;for (int i = 0; i < index - 1; i++) prev = prev.next;prev.next = prev.next.next;}length--;}
}/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList obj = new MyLinkedList();* int param_1 = obj.get(index);* obj.addAtHead(val);* obj.addAtTail(val);* obj.addAtIndex(index,val);* obj.deleteAtIndex(index);*/
// @lc code=end
反转链表
头插法解决
/** @lc app=leetcode.cn id=206 lang=java** [206] 反转链表*/// @lc code=start
/*** 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) {if (head == null || head.next == null) {return head;}ListNode temp = new ListNode();ListNode result = new ListNode();ListNode a = new ListNode();temp.next = head;while (temp.next != null) {temp = temp.next;a = new ListNode(temp.val);a.next = result.next;result.next = a;}return result.next;}
}
// @lc code=end