第二章 链表part01
链表理论基础,203.移除链表元素,707.设计链表,206.反转链表
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) { //设置虚拟头结点 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; } }
707.设计链表
定义结构体时并没有使用虚拟头节点,后续各种操作接口里用了。
记录一下注意点,用虚拟头节点时最后要加一句head = dummyNode.next,因为可能头节点已经被改动了。
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 MyLinkedList { // 链表元素个数 int size; // 头节点 ListNode head; // 无参构造方法 public MyLinkedList() { size = 0; head = null; } public int get(int index) { // 获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1 if (index < 0 || index > size - 1) { return -1; } ListNode cur = head; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.val; } public void addAtHead(int val) { // 将一个值为val的节点插入到链表中第一个元素之前。 // 在插入完成后,新节点会成为链表的第一个节点。 // 虚拟头结点为新节点 ListNode dummyNode = new ListNode(val); dummyNode.next = head; // head指向新节点 head = dummyNode; size++; } public void addAtTail(int val) { // 将一个值为 val 的节点追加到链表中作为链表的最后一个元素 // 虚拟头结点 ListNode dummyNode = new ListNode(); dummyNode.next = head; // cur遍历 到最后一个元素 ListNode cur = dummyNode; while (cur.next != null) { cur = cur.next; } // 加元素 cur.next = new ListNode(val); size++; head = dummyNode.next; } public void addAtIndex(int index, int val) { // 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。 // 如果 index 等于链表的长度,那么该节点会被追加到链表的末尾。 // 如果 index 比长度更大,该节点将 不会插入到链表中. if (index > size || index < 0) { return; } if (index == size) { addAtTail(val); } else { // 虚拟头结点 ListNode dummyNode = new ListNode(); dummyNode.next = head; // cur遍历 到index前节点 ListNode cur = dummyNode; for (int i = 0; i < index; i++) { cur = cur.next; } // 加元素 ListNode toAdd = new ListNode(val); toAdd.next = cur.next; cur.next = toAdd; size++; head = dummyNode.next; } } // 如果下标有效,则删除链表中下标为 index 的节点 public void deleteAtIndex(int index) { if (index >= 0 && index < size) { // 虚拟头结点 ListNode dummyNode = new ListNode(); dummyNode.next = head; // pre 遍历至前驱节点 ListNode pre = dummyNode; for (int i = 0; i < index; i++) { pre = pre.next; } // 删除 pre.next = pre.next.next; head = dummyNode.next; size--; } } }
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) { ListNode pre = null; ListNode cur = head; while (cur!= null){ // 存一下下一个节点 ListNode nex = cur.next; // 翻转当前节点指向 cur.next = pre; // 移动指针 pre = cur; cur = nex; } return pre; } }