【链表专题】

链表专题】"/>

【链表专题】

链表专题

• • 移除链表元素
  • 设计链表
  • 反转链表

移除链表元素

• 移除链表元素（Leetcode:203）
  给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
  

/*** 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 null;}//定义虚拟头节点ListNode dummy = new ListNode(-1, head);ListNode pre = dummy;ListNode cur = head;//删除指定元素的值节点while(cur != null) {if (cur.val == val) {pre.next = cur.next;} else {pre = cur;}cur = cur.next;}//返回新的链表的头节点return dummy.next;}
}

设计链表

• 设计链表（Leetcode:707）
  

class ListNode {int val;ListNode next;public ListNode() {}public ListNode(int val) {this.val = val;}public ListNode(int val, ListNode next) {this.val = val;this.next = next;}}class MyLinkedList {//size存储链表元素的个数int size;//虚拟头节点ListNode head;//初始化链表public MyLinkedList() {size = 0;head = new ListNode(0);}//获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点public int get(int index) {if (index < 0 || index >= size) {return -1;}//当前指针先指向虚拟头节点ListNode cur = head;for (int i = 0; i <= index; i++) {cur = cur.next;}return cur.val;}//在链表最前面插入一个节点，等价于在第0个元素前添加public void addAtHead(int val) {addAtIndex(0, val);}public void addAtTail(int val) {addAtIndex(size, val);}public void addAtIndex(int index, int val) {if (index > size) {return;}if (index < 0) {index = 0;}size++;ListNode pre = head;for (int i = 0; i < index; i++) {//举个极端的在末尾插入的例子，如数组[1]，在index为1处插入元素，循环结束会出现pre指向null的情况，导致引用失效，所以i不能=indexpre = pre.next;}ListNode toAdd = new ListNode(val);toAdd.next = pre.next;pre.next = toAdd;}public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}size--;if (index == 0) {head = head.next;return;}ListNode pre = head;for (int i = 0; i < index; i++) {//极端例子，考虑到pre和pre.next都不能为空；如[1,2,3]删除index为2的元素，pre = pre.next;}pre.next = pre.next.next;}
}/*** 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);*/

反转链表

• 反转链表（Leetcode:206）

/*** 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) {//双指针法：先定义两个指针pre和cur分别指向null和head,一个临时指针tempListNode pre = null;ListNode cur = head;ListNode temp = null;while (cur != null) {//循环遍历//临时指针先存放cur.next,因为它等会会改变方向，避免丢失引用temp = cur.next;//改变指针指向，由指向后一个节点改为指向前一个节点cur.next = pre;//移动pre, cur向后移，继续后续的反转的过程pre = cur;cur = temp;}return pre;}
}