1. 分割链表
OJ链接
class Solution {
public ListNode partition(ListNode head, int x) {
if(head == null){
return null;//空链表的情况
}
ListNode cur = head;
ListNode formerhead = null;
ListNode formerend = null;
ListNode latterhead = null;
ListNode latterend = null;//定义链表分区
while (cur != null){//遍历链表
if(cur.val < x){
if(formerhead == null){
formerhead = cur;
formerend = cur;//第一次遍历头和尾都为null
//formerend = formerend.next;错误,不可以使得formerend向下走,否者为null,会空指针异常
}else{
formerend.next = cur;
formerend = formerend.next;//formerend全程不可以为空
}
}
if(cur.val >= x){
if(latterhead == null){
latterhead = cur;
latterend = cur;
}else{
latterend.next = cur;
latterend = latterend.next;
}
}
cur = cur.next;
}
if(formerhead == null){//链表前段位空时的情况,formerend为空,下面会报异常
return latterhead;
}
if(latterhead != null){//当链表后段不为空时,(为空不走这一步,否则空指针异常),链表的最后需要手动置为null
latterend.next = null;
}
formerend.next = latterhead;//之所以上面要求formerend全程不为空,是因为这一步会报异常,null
return formerhead;
}
}
整体思路:
创建一个新的链表,把这个新的链表用x分段,遍历原链表,根据条件把结点放入新链表,之后把前面一段链表和后面一段链表连接起来.
[注意事项]
- 要始终保持fe(formerend)不为空,否者在最后连接的时候就要报空指针异常
- 考虑几种特殊情况
- 链表为空,返回null
- 前半段链表为空,在最后连接的时候会报空指针异常,所以在最后的时候返回lb即可.
- 当后半段链表不为空的时候,最后一个结点的next有可能不为null,所以要对最后手动置空,否者会越界.
动态演示
分割链表
2. 回文链表
OJ链接
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null){//空链表情况下
return true;
}
ListNode fast = head;
ListNode slow = head;
ListNode cur = null;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;//找到中间结点
}
cur = slow.next;
while(cur != null){
ListNode curNext = cur.next;//在循环体中定义ListNode,防止空指针异常
cur.next = slow;
slow = cur;
cur = curNext;
}//翻转后半段链表
cur = head;
while(cur != slow){//奇数判断回文
if(cur.val != slow.val){
return false;
}
if(cur.next == slow){//偶数判断回文
return true;
}
cur = cur.next;
slow = slow.next;
}
return true;
}
}
整体思路:
先使用快慢指针找到中间节点,之后将后半段链表使用头插法翻转.之后把head和slow向中间遍历,相遇就是回文.
[注意事项]
- 注意区分奇偶数,奇数整体思路没问题,但是偶数永远不会相遇,此时就需要引入
if(cur.next == slow)判断偶数情况.
动态演示
回文链表(偶数)
回文链表(奇数)
3. 相交链表
OJ链接
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = 0;
int lenB = 0;
ListNode cur = headA;
while(cur != null){
lenA++;
cur = cur.next;
}
cur = headB;
while(cur != null){
lenB++;
cur = cur.next;
}//计算两个链表的长度
int len = lenA-lenB;//计算长度之差,但是有可能为负数
ListNode longList = headA;
ListNode shortList = headB;//定义长链表和短链表,如果len为正,则longList为A,另一个为B
if(len < 0){//负数则相反
longList = headB;
shortList = headA;
len = lenB-lenA;//把len变为正数
}
while(len != 0){
longList = longList.next;
len--;//先让长链表走差值步
}
while(longList != shortList){
longList = longList.next;
shortList = shortList.next;//之后一起走,直到相交
}
if(longList == null || shortList == null){
return null;//没有交点的情况
}
return longList;//返回交点
}
}
整体思路
先让长链表走短链表与长链表的差值步,之后一起走,相遇之后就有交点.
[注意事项]
- 不确定哪个链表长,哪个链表短,所以长度的差值可能为负数.我们定义长链表和短链表来解决这个问题,利用长度的差值来判断长短.
- 有一个非常隐形的问题,链表可能不想交,所以我们要用
if(longList == null || shortList == null)来限制.虽然没有这句话也可以跑过,是因为最后longList和shortList都走到了null,返回longList正好也是null.所以这个问题非常隐性.
动态演示
相交链表
4. 环形链表
OJ链接
ublic class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){//先以无环作为跳出循环的条件,因为是快指针,所以两个条件缺一不可
fast = fast.next.next;
slow = slow.next;
if(slow == fast){//在走的过程中再判断什么时候相等,返回即可
return true;
}
}
return false;
}
}
整体思路
定义一个快指针,一个慢指针,快指针一次走两步,慢指针一次走一步,最终进入环的时候必定会相遇.相遇一定就有环.
[注意事项]
- 首先判断的是链表有没有环,这是循环的条件.
- 在循环体内部再判断会不会相遇.
动态演示
环形链表
5. 寻找环形链表的环入口
OJ链接
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){//无环情况
fast = fast.next.next;
slow = slow.next;
if(fast == slow){//相遇的情况
while(head != slow){
head = head.next;
slow = slow.next;//向环的入口靠近
}
return slow;//相遇的位置即为入口
}
}
return null;
}
}
整体思路
先找到相遇的点,之后根据数学推导可知,链表头到入口的距离与相遇点到入口的距离相等,让head和slow同时向入口处走,相遇的地方就是要返回的点.
[数学推导]
动态演示
寻找环的入口
