- 前几天忙比赛，算法停了三天，继续开刷，不能停！！
二、链表
2.1删除链表中的元素
两种方案
-
无哨头：要删除节点的前一个结点指向删除节点的指向节点。头节点需要单独定义
-
有哨头：头节点不需要单独定义
-
实战
力扣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 current = new ListNode(0);current.next = head;ListNode temp = current;while (temp.next != null) {if (temp.next.val == val) {temp.next = temp.next.next;}else {temp = temp.next;}}return current.next;} } -
使用哨头，只需定义删除方法
要删除节点的前一个结点指向删除节点的指向节点即可。
-
2.2实现单向链表
-
链表的crud
-
实战
力扣707
class MyLinkedList {ListNode vhead;int size;public MyLinkedList() {vhead = new ListNode(0);size = 0;}public int get(int index) {if (index < 0 || index >= size) {return -1;}ListNode temp = vhead;for (int i = 0; i <= index; ++i) {temp = temp.next;}return temp.val;}public void addAtHead(int val) {ListNode temp = new ListNode(val);temp.next = vhead.next;vhead.next = temp;size++;}public void addAtTail(int val) {ListNode temp = vhead;for (int i = 0; i < size; ++i) {temp = temp.next;}ListNode t = new ListNode(val);temp.next = t;size++;}public void addAtIndex(int index, int val) {if (index > size || index < 0) {return;}ListNode temp = vhead;for (int i = 0; i < index; ++i) {temp = temp.next;}ListNode t = new ListNode(val);t.next = temp.next;temp.next = t;size++;}public void deleteAtIndex(int index) {ListNode temp = vhead;if (index < 0 || index >= size) {return;}else {for (int i = 0; i < index; ++i) {temp = temp.next;}temp.next = temp.next.next;size--;}} } -
我是用头哨实现的，是一个虚拟节点，注意形参和实际参数的区别，需要做转换，链表内部index:0是虚拟节点不允许访问，外部访问index:0，其实就是访问index:1的节点
-
2.3双指针法
-
翻转链表
-
实战
力扣206
迭代法
class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;} } -
此解较为常见，链表题最重要的是（我是谁、我下一个节点是谁、我上一个节点是谁），在修改当前节点的next指针的时候，注意存储以防断链
递归法（递归其实就是后一项依靠前一项，这里依靠的是翻转后头节点）
此题递归需要传递的点就是反转后的头节点，此解法采用先返回反转后头节点再翻转。要注意递归传递的是翻转头节点，不是当前节点是下一个节点，因为链表本身就具有记忆的能力，把这个当作传递点会很多余。而无法传递的是翻转后头节点，所以传递它
class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode newNode = reverseList(head.next);head.next.next = head; // 翻转head.next = null; // 将原来的链接置空return newNode;} }class Solution {public ListNode reverseList(ListNode head) {return reverse(null, head);}private ListNode reverse(ListNode prev, ListNode cur) {if (cur == null) {return prev;}ListNode temp = null;temp = cur.next;// 先保存下一个节点cur.next = prev;// 反转return reverse(cur, temp);} }
-
-
两两交换链表中的节点
-
实战
力扣
双指针+虚拟头节点
class Solution {public ListNode swapPairs(ListNode head) {ListNode vhead = new ListNode(0);vhead.next = head;ListNode slow; // 不提前赋值，防止空链表需要额外判断ListNode fast;ListNode temp = vhead;while(temp.next != null && temp.next.next != null) {slow = temp.next; // 通过temp赋值，也减少循环判断fast = temp.next.next;slow.next = fast.next;fast.next = slow;temp.next = fast;temp = slow;}return vhead.next;} } -
交换节点需要三步，slow指向fast.next，fast指向slow，temp指向temp，这个时候交换好了，但是需要跳转然后继续交换，这里体现了虚拟头节点的好处，跳转后交换，fast要与前一个交换后的slow相连接，这里就可以通过虚拟头节点代替。
-
递归（这里递归传递的是后两个节点，因为头节点一开始交换后就可以确定）
class Solution {public ListNode swapPairs(ListNode head) {if(head == null || head.next == null) return head;// 获取当前节点的下一个节点ListNode next = head.next;// 进行递归ListNode newNode = swapPairs(next.next);// 这里进行交换next.next = head;head.next = newNode;return next;} }
-
-
删除链表的第N个节点
-
实战
力扣19
典型的双指针，让快指针走n步，然后快慢指针同时走，快指针走到最后一个节点，慢指针就到了要删除节点的前一个节点
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode vhead = new ListNode(0);vhead.next = head;ListNode fastPtr = vhead;ListNode slowPtr = vhead;for (; n > 0; --n) {fastPtr = fastPtr.next;}while (fastPtr.next != null) {fastPtr = fastPtr.next;slowPtr = slowPtr.next;}slowPtr.next = slowPtr.next.next;return vhead.next;} }
-
-
链表相交
-
实战
力扣160
长的链表的起始部分短的链表一定不包含，第一步就是剪切那一部分，然后进行一一比对，如果节点相等说明相交
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/ public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int num_A = 0;int num_B = 0;ListNode skipA = headA;ListNode skipB = headB;while (headA != null){headA = headA.next;num_A++;}while (headB != null){headB = headB.next;num_B++;}if (num_A >= num_B) {int m = num_A - num_B;for (int i = 0; i < m; i++) {skipA = skipA.next;}while (skipA != null) {if (skipA == skipB) {return skipA;}else {skipA = skipA.next;skipB = skipB.next;}}}else {int m = (num_A - num_B) * -1;for (int i = 0; i < m; i++) {skipB = skipB.next;}while (skipA != null) {if (skipA == skipB) {return skipA;}else {skipA = skipA.next;skipB = skipB.next;}}}return null;} } -
这里直接调HashSet表，去重复，更容易
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Set<ListNode> visited = new HashSet<ListNode>();ListNode temp = headA;while (temp != null) {visited.add(temp);temp = temp.next;}temp = headB;while (temp != null) {if (visited.contains(temp)) {return temp;}temp = temp.next;}return null;} }
-
-
环形链表
-
实战
力扣142
哈希表秒杀
public class Solution {public ListNode detectCycle(ListNode head) {ListNode pos = head;Set<ListNode> visited = new HashSet<ListNode>();while (pos != null) {if (visited.contains(pos)) {return pos;} else {visited.add(pos);}pos = pos.next;}return null;} }双指针写法，慢指针每次走一步，快指针每次走两步，如果有环，那么一定会相遇，因为当慢指针到环的时候，快制作一定到了，这个时候相当于快指针追慢指针，每次挪一步，一定会追到。而且慢指针一定不会走满一圈。举例，在极限位置再过一点不符合条件，就是当满指针刚进环的时候，两指针就相遇了，这个时候先不算，由于快指针是慢指针的两倍速，所以最多再经历完一圈快指针追上慢指针，而这种实际不可能，快指针会更快一步。
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;ListNode index1 = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (slow == fast) {ListNode index2 = slow;while (index2 != index1) {index1 = index1.next;index2 = index2.next;}return index1;}}return null;} }
-