【牛客网刷题记录】【java】链表

（1）反转链表

链接
可以说是最经典的链表题目之一，并且很多人经常会记不得怎么做。
但大致思路是比较简单的，重点就是如何用指针对链表进行反转的同时还不能丢失链表。不可避免的就是需要一个指针指向已经反转的部分（pre），另一个是指向仍未反转的部分（cur)。
例如节点是A->B->C, pre指向A，cur指向B，每次用cur向后移动（C），代表待反转的变少，pre要移动到B，并且将B的next指向A，这就需要多一个tmp指针。

JAVA：

public class Solution {public ListNode ReverseList (ListNode head) {ListNode pre=null, cur=head, tmp=null;while(cur!=null){tmp=cur;cur=cur.next;tmp.next=pre;pre=tmp;}return tmp;}
}

（2）链表内指定区间反转

链接

最简单的方法就是，将需要反转的部分提出，反转后再放回去。

public class Solution {/*** * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类*///说明：方便理解，以下注释中将用left，right分别代替m,n节点 public ListNode reverseBetween (ListNode head, int m, int n) {//设置虚拟头节点ListNode dummyNode = new ListNode(-1);dummyNode.next = head;ListNode pre = dummyNode;//1.走left-1步到left的前一个节点for(int i=0;i<m-1;i++){pre = pre.next;}//2.走roght-left+1步到right节点ListNode rigthNode = pre;for(int i=0;i<n-m+1;i++){rigthNode = rigthNode.next;}//3.截取出一个子链表ListNode leftNode = pre.next;ListNode cur = rigthNode.next;//4.切断链接pre.next=null;rigthNode.next=null;//5.反转局部链表reverseLinkedList(leftNode);//6.接回原来的链表pre.next = rigthNode;leftNode.next = cur;return dummyNode.next;}//反转局部链表private void reverseLinkedList(ListNode head){ListNode pre = null;ListNode cur = head;while(cur!=null){//Cur_next 指向cur节点的下一个节点ListNode Cur_next = cur.next;cur.next = pre;pre = cur;cur = Cur_next ;}}
}

（3）合并两个排序的列表

链接
说实话，这题我认为递归是最清晰且好理解的。
两个链表的元素怎么衔接节点大致有如下考虑：例如有a和b节点，a小于b并不能说明a后面要衔接b，因为a的后一个值可能大于b。因此要判断到a小于b且a后的值大于b。同时，如果出现了一个链表已经遍历完后，可以直接加在后面（类似于归并排序）。
但这样的问题就是代码会比较冗余，因为需要判断现在谁是更小的节点。如果用递归，则可以很自然的处理那个节点的值更小的情况。我们每次判断当前的a和b节点谁更小，将小的值的下一个节点和大的节点放入递归即可。

public ListNode Merge (ListNode pHead1, ListNode pHead2) {// 特判为空if(pHead1==null || pHead2==null){return pHead1==null? pHead2 : pHead1;}if(pHead1.val<=pHead2.val){pHead1.next=Merge(pHead1.next, pHead2);return pHead1;}else{pHead2.next=Merge(pHead1, pHead2.next);return pHead2;}}

或者使用迭代来写，也比较简单。创建一个dummy节点，将剩余的节点续在dummy后面：

 public ListNode Merge (ListNode pHead1, ListNode pHead2) {// 特判为空if (pHead1 == null || pHead2 == null) {return pHead1 == null ? pHead2 : pHead1;}ListNode dummy = new ListNode(0);ListNode p1 = pHead1, p2 = pHead2, tmp=dummy;while(p1!=null&&p2!=null){if(p1.val<p2.val){tmp.next=p1;p1=p1.next;}else{tmp.next=p2;p2=p2.next;}tmp=tmp.next;}tmp.next = (p1 == null) ? p2 : p1;return dummy.next;}

（4）合并k个已排序的链表

链接
最开始的思路就像是做归并（多路归并，常用于磁盘），用一个tmpList存储lists里的子链表的头指针，然后再每次选出最小的指针，将该指针指向的内容挂到dummy的后面。这样的思路很类似与归并排序。
在这里插入图片描述
而这样的操作可以进一步简化，不需要加入tmplist：这是因为表面上看lists是一个arraylist，每个元素是一串链表，但实际上每个元素存储的还是指针，而后续的链表节点都是由指针连接起来的。因此lists和我们设想的tmplist其实是一样的。
我们要做的是：每次从list的子链表选一个最小的，用minNode这个指针进行表示。添加到res后，minNode向后移动。这里的set方法是更新 lists 中对应链表的当前节点。

public ListNode mergeKLists(ArrayList<ListNode> lists) {if (lists == null || lists.size() == 0) {return null;}ListNode dummy = new ListNode(0);ListNode res = dummy;int len = lists.size();while (true) {ListNode minNode = null;int minFlag = -1;// 找到当前最小节点for (int i = 0; i < len; i++) {ListNode node = lists.get(i);if (node != null && (minNode == null || node.val < minNode.val)) {minNode = node;minFlag = i;}}// 如果所有链表都遍历完了，跳出循环if (minNode == null) {break;}// 将最小节点添加到结果链表中res.next = minNode;res = res.next;// 更新对应链表的当前节点lists.set(minFlag, minNode.next);}return dummy.next;
}

顺便说一下：

lists.get(minFlag)=lists.get(minFlag).next;

这样的操作是不合法的。代码本意是想表达将minFlag位置的内容（即指针）指向下一个元素，但是在Java中，方法调用的结果是一个值，而不是一个可以赋值的左值，即lists.get(minFlag) 是一个方法调用的结果，它返回一个 ListNode 对象的引用，但这个引用本身不是一个可以赋值的变量。
为了更新 ArrayList 中的元素，你需要使用 ArrayList 的 set 方法。set 方法允许你指定索引并更新该索引处的元素。例如：

lists.set(minFlag, lists.get(minFlag).next);

上面的代码可以完成要求，但每次需要找到子列表的最小值，这就增加了操作，提高了时间复杂度。我们可以考虑用最小堆（优先队列）来优化：

public ListNode mergeKLists(ArrayList<ListNode> lists) {if (lists == null || lists.size() == 0) {return null;}ListNode dummy = new ListNode(0);ListNode res = dummy;// 使用优先队列（最小堆）来优化查找最小节点的过程PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);//(a, b) -> a.val - b.val：这是一个Lambda表达式，用于定义比较器。// 初始化优先队列for (ListNode node : lists) {if (node != null) {pq.add(node);}}while (!pq.isEmpty()) {ListNode minNode = pq.poll();res.next = minNode;res = res.next;if (minNode.next != null) {pq.add(minNode.next);}}return dummy.next;}

对于lambda表达式：在Java中，Comparator 接口用于定义对象的比较规则。PriorityQueue 使用这个比较器来确定元素的顺序。比较器的 compare 方法通常返回一个整数值，用于表示两个对象的相对顺序：

负值：表示第一个对象小于第二个对象。
零：表示两个对象相等。
正值：表示第一个对象大于第二个对象。

(5) 判断链表中是否有环

链接
很经典的题目，用快慢指针可以很快的得到是否成环。如果成环，快指针肯定会追上慢指针。

public class Solution {public boolean hasCycle(ListNode head) {ListNode fast=head, slow=head;while(fast!=null && fast.next!=null){slow = slow.next;fast = fast.next.next;if(fast==slow){return true;}}return false;}
}

（6）链表中环的入口结点

链接
上面的题目的进阶，这次还要判断入口在哪里。因为双指针相遇的地方不会是入口，因此直接返回slow是不对的。这里需要一些数学推理：
在这里插入图片描述
这里设slow和fast走的距离是Lslow和Lfast，环之前的长度为a，环长度为b，换入口到相遇地点长度为x。那么则有：

Ls=a+x
Lf=2a+2x=a+b+x
可以得到a=b-x，也就是新的指针（ptr）从头开始走到入口和slow继续走到入口的距离一样，因此第二个循环则是针对这两个指针。

public ListNode EntryNodeOfLoop(ListNode pHead) {ListNode slow=pHead, fast=pHead, ptr=pHead;boolean flag=false;while(fast!=null && fast.next!=null){slow=slow.next;fast=fast.next.next;if(slow==fast){flag=true;break;}}// 判断是否有环，如果没有环，则返回nullif(flag==false){return null;}while(true){if(slow==ptr){break;}slow=slow.next;ptr=ptr.next;}return slow;}

（7）链表中倒数最后k个结点

链接
也算快指针的做法，先让快指针走k个（有dummy节点），之后再让slow和fast同时走，即可找到倒数的节点。注意输入样例会有超出链表长度的输入，加入判断语句即可。

public ListNode FindKthToTail (ListNode pHead, int k) {// write code hereListNode dummy=new ListNode(-1);dummy.next=pHead;ListNode fast=dummy, res=pHead;for(int i=0; i<k; i++){fast=fast.next;if(fast==null){return null;}}while(fast.next!=null){fast=fast.next;res=res.next;}return res;}

（8）两个链表的第一个公共结点

链接
在这里插入图片描述
也是数学推理，假设第一个链表到交点之前的长度为a，第二个链表到交点之前的长度为b，公共长度为x。因此如果指针遍历完自己的链表，再跳转到另一个链表遍历，那么两个指针一定会在交点相遇。

a+x+b=b+x+a
这样可以得到代码：

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {ListNode ptr1=pHead1, ptr2=pHead2;while(ptr1!=ptr2){ptr1 = (ptr1 != null) ? ptr1.next : pHead2;ptr2 = (ptr2 != null) ? ptr2.next : pHead1;}return ptr1;}