文章目录
JZ23 链表中环的入口结点
题目描述
思路详解
本题采用快慢指针的思路解题。
对于判断有没有环，利用环没有末尾NULL，后半部分一定是环，然后快慢双指针相遇就代表有环。
那我们现在假定已经是一个有环的链表了，那么这个链表中怎么找到环的入口呢？在慢指针进入链表环之前，快指针已经进入了环，且在里面循环，这才能在慢指针进入环之后，快指针追到了慢指针，不妨假设快指针在环中走了n圈，慢指针在环中走了m圈，它们才相遇，而进入环之前的距离为x，环入口到相遇点的距离为y，相遇点到环入口的距离为z。快指针一共走了x+n(y+z)+y步，慢指针一共走了x+m(y+z)+y，这个时候快指针走的倍数是慢指针的两倍，则x+n(y+z)+y=2(x+m(y+z)+y)，这时候x+y=(n−2m)(y+z)。因为环的大小是y+z，说明从链表头经过环入口到达相遇地方经过的距离等于整数倍环的大小：那我们从头开始遍历到相遇位置，和从相遇位置开始在环中遍历，会使用相同的步数，而双方最后都会经过入口到相遇位置这y个节点，那说明这y个节点它们就是重叠遍历的，那它们从入口位置就相遇。
代码与结果
import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ public class Solution { //判断有没有环，返回相遇的地方 public ListNode hasCycle(ListNode head) { //先判断链表为空的情况 if(head == null) return null; //快慢双指针 ListNode fast = head; ListNode slow = head; //如果没环快指针会先到链表尾 while(fast != null && fast.next != null){ //快指针移动两步 fast = fast.next.next; //慢指针移动一步 slow = slow.next; //相遇则有环，返回相遇的位置 if(fast == slow) return slow; } //到末尾说明没有环，返回null return null; } public ListNode EntryNodeOfLoop(ListNode pHead) { ListNode slow = hasCycle(pHead); //没有环 if(slow == null) return null; //快指针回到表头 ListNode fast = pHead; //再次相遇即是环入口 while(fast != slow){ fast = fast.next; slow = slow.next; } return slow; } }
JZ24 反转链表
题目描述
思路详解
最简单的一种方式就是使用栈，因为栈是先进后出的。实现原理就是把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表。
代码与结果
import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode ReverseList(ListNode head) { Stack<ListNode> stack= new Stack<>(); //把链表节点全部摘掉放到栈中 while (head != null) { stack.push(head); head = head.next; } if (stack.isEmpty()) return null; ListNode node = stack.pop(); ListNode dummy = node; //栈中的结点全部出栈，然后重新连成一个新的链表 while (!stack.isEmpty()) { ListNode tempNode = stack.pop(); node.next = tempNode; node = node.next; } //最后一个结点就是反转前的头结点，一定要让他的next //等于空，否则会构成环 node.next = null; return dummy; } }
JZ25 合并两个排序的链表
题目描述
思路详解
从头结点开始考虑，比较两表头结点的值，值较小的list的头结点后面接merge好的链表（进入递归了）；
若两链表有一个为空，返回非空链表，递归结束；
当前层不考虑下一层的细节，当前层较小的结点接上该结点的next与另一结点merge好的表头就ok了；
每层返回选定的较小结点就ok；
终止条件：两链表其中一个为空时，返回另一个链表；
当前递归内容：若list1.val <= list2.val 将较小的list1.next与merge后的表头连接，即list1.next = Merge(list1.next,list2); list2.val较大时同理；
每次的返回值：排序好的链表头；
代码与结果
import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null){ return list2; } else if(list2==null){ return list1; } if(list2.val>list1.val){ list1.next = Merge(list1.next,list2); return list1; } else{ list2.next = Merge(list1,list2.next); return list2; } } }
