- 前几天忙比赛，算法停了三天，继续开刷，不能停！！
二、链表
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; } }
-