Java 单向列表的几种操作方式(删除，查找环，环入口)

2024-02-08 14:28| 来源: 网络整理| 查看: 265

Java ⼆叉树操作

本文章的列表为单项列表。

列表的节点类，类的内容包括数据int 和下一个节点的指向。

class Node{ int data; Node next; public Node(int data,Node next) { this.data = data; this.next = next; } }

1.删除节点操作

1.1是头节点为空

1.2删除节点在链表的尾部，即删除p4

1.3删除节点在链表的中间位置即删除

对应的Java代码如下:

public static void deleteNode(Node head, Node node) { if (head == node) { head = null; } else if (node.next == null) { while (head.next != node) { head = head.next; } head.next = null; } else { Node q = node.next; node.data = q.data; node.next = q.next; } }

2.删除指定数值的节点

2.1方案一：将数值data不等于num的节点存放到栈中，然后拿到栈的队列，然后进行出栈操作返回头节点。如图删除data是3的节点。

对应代码

public Node removeValue(Node head,int num) { Stack stack = new Stack(); while (head != null) { if (head.data != num) { stack.push(head); } head = head.next; } while (!stack.isEmpty()) { stack.peek().next = head; head = stack.pop(); } return head; }

2.2 方案二：首先判断要删除的数字是否在节点的前几位，如果在节点的头几位，先遍历到要返回的头节点，如果删除的节点，不在头节点，就进行遍历删除操作。图片是删除数值1的节点，head指向了p2 ,之后的节点用过链表遍历删除。

public Node removeValue2(Node head,int num) { while(head != null) { if (head.data != num) { break; } head = head.next; } Node pre = head; Node cur = head; while (cur != null) { if (cur.data != num) { pre.next = cur.next; } else { cur = pre; } cur = cur.next; } return head; }

3.删除重复节点：

方案是利用HasSet的存值不可重复性，开始存储节点的值，如果节点的值在HashSet中存在，即表明此值是重复值。

public void deleteDuplication(Node head) { if (head == null) { return; } HashSet set = new HashSet(); Node pre = head; Node cur = head.next; set.add(head.data); while (cur != null) { if (set.contains(cur.data)) { pre.next = cur.next; } else { set.add(cur.data); pre = cur; } cur = cur.next; } }

4.检查列表是否有环

假设链表是一个有环链表，且由P4指向P2构成环。那么使用两个指针 S 和 L，

让两指针同时向后遍历而且L的遍历速度是S的两倍，呢么如果是有环的话，

S终究会追上L。因此我们可以以SL是否相遇作为判断是否有环的必要条件。

如图中的案例，SL在第散步相遇。证明有环的存在

public boolean isLoop(Node head){ // TODO 定义两个指针，分别是S和L Node L= first; Node S= first; // TODO 遍历一遍链表，如果最后是null的话就代表没有环 while ( L != null && L.next != null){ L = L.next.next; S = S.next; //如果俩相遇了，代表有环 if (L == S){ return true; } } return false; }

5.检查查找单列表否的入口

如图所展示，这是一个有环列表的模型，S、L分别指向头节点，P为环的入口点，K为上个方法查询链表是否为环的相遇点。

接下来我们将环列表由P也就是环的入口处拆开成一条直线进行查看

我们将链表分为几个线段，分别是，a 是链表头到环入口的长度，b是环入口到S L相遇点的长度，c是相遇点再到P的长都，d是P到P环的长度

我们在查找链表是否是环的问题上利用的是 S走过的长度是L的二倍，也就是说相同时间 S和L相遇的时候 S的路程是L的路程的两倍。

可得出如下结论:

2 * (a + b) = n * d +b +a ; 其中 n指的是 S节点在列表里面由P到P循环走过的次数 >=1；

由于 b = d - c；

a +d - c =n * d

a = c + (n-1) * d

所以 a和c 是差了 (n-1) * d 个而d就是 p到p的距离，因为n必须是正整数所以正整数 (n-1) * d可以忽略不计

等式就变成了

a = c

所以要是闭环的情况下S走过P 和L从头节点走过P时必定相遇。

我们将L重新放到头节点然后将S从相遇节点往后遍历，当S在环中循环n次之后，会和L在节点入口处相遇。

具体的代码:

public ListNode detectCycle(ListNode head) { ListNode S= head; ListNode L= head; while(S!= null && S.next != null){ S= S.next.next; L= L.next; if(S== L){ break; } } if(S== null || S.next == null){ return null; } L= head; while(S!= slow){ L= L.next; S= S.next; } return L; }

【本文地址】

公司简介

联系我们