资料来自代码随想录 (programmercarl.com)
基础知识
链表由数据域和指针域两部分组成,最后一个节点的指针域指向null
- 单链表:只能单向查询
- 双链表:每一个节点有两个指针域,一个指向下一个节点,一个指向上一个节点,可以双向查询
- 循环链表:形成一个环的链表
链表的定义
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| 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; } }
|
移除链表的元素
203. 移除链表元素 - 力扣(LeetCode) (leetcode-cn.com)
普通方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| public ListNode removeElements(ListNode head, int val) {
while ( head!=null&&head.val==val ){ head=head.next; } if(head==null){ return head; } ListNode preNode=head; ListNode curNode=head.next; while (curNode != null) { if (curNode.val==val){ preNode.next=curNode.next; }else { preNode=curNode; } curNode=curNode.next; }
return head; }
|
特殊方法
添加虚拟节点的方式,使得头节点也加入常规之中,规避了头节点为空的复杂情况
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| public ListNode removeElements(ListNode head, int val) { if(head==null){ return head; }
ListNode dummy=new ListNode(-1,head); ListNode preNode=dummy; ListNode curNode=head; while (curNode != null) { if (curNode.val==val){ preNode.next=curNode.next; }else { preNode=curNode; } curNode=curNode.next; }
return dummy.next; }
|
其他题目
https://moonshuo.cn/posts/54869.html
链表相交
面试题 02.07. 链表相交 - 力扣(LeetCode)
普通方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode tempA = headA;
while (tempA != null) { ListNode tempB = headB; while (tempB != null) { if (tempA == tempB) { return tempA; } else { if (tempB.next != null) { tempB = tempB.next; } else { break; } } } if (tempA.next != null) { tempA = tempA.next; } else { return null; } } return null; }
|
哈希表方法
我们这里可以使用哈希表的特性,遍历两个节点,将这些值存入到哈希表中
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| public ListNode getIntersectionNode(ListNode headA, ListNode headB) { HashSet<ListNode> hashSet = new HashSet<>(); ListNode tempA = headA; while (tempA != null) { hashSet.add(tempA); if (tempA.next != null) { tempA = tempA.next; } else { break; } } ListNode tempB = headB; while (tempB != null) { if (!hashSet.add(tempB)) { return tempB; } else { if (tempB.next != null) { tempB = tempB.next; }else { break; } } } return null; }
|
双指针方法
这个双指针非常巧妙的经过依次调换之后,将两个指针指到了相交节点前的相同的位置,简单
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA, pB = headB; while (pA != pB) { pA = pA == null ? headB : pA.next; pB = pB == null ? headA : pB.next; } return pA; }
|
判断环形链表
142. 环形链表 II - 力扣(LeetCode)
普通方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
|
public class Solution { public ListNode detectCycle(ListNode head) { HashSet<ListNode> listNodes=new HashSet<>();
ListNode temp=head; while (temp!=null){ if (!listNodes.add(temp)){ return temp; }else { temp=temp.next; }
} return null; } }
|
双指针法
将寻找环的过程转换为追击问题,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| public class Solution { public ListNode detectCycle(ListNode head) { if (head == null) { return null; } ListNode slow = head, fast = head; while (fast != null) { slow = slow.next; if (fast.next != null) { fast = fast.next.next; } else { return null; } if (fast == slow) { ListNode ptr = head; while (ptr != slow) { ptr = ptr.next; slow = slow.next; } return ptr; } } return null; } }
|