Collection与数据结构 链表与LinkedList(三):链表精选OJ例题(下)

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){//当链表后段不为空时,(为空不走这一步,否则空指针异常),链表的最后需要手动置为nulllatterend.next = null;}formerend.next = latterhead;//之所以上面要求formerend全程不为空,是因为这一步会报异常,nullreturn formerhead;}
}

整体思路:
创建一个新的链表,把这个新的链表用x分段,遍历原链表,根据条件把结点放入新链表,之后把前面一段链表和后面一段链表连接起来.

[注意事项]

1. 要始终保持fe(formerend)不为空,否者在最后连接的时候就要报空指针异常
2. 考虑几种特殊情况

• 链表为空,返回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向中间遍历,相遇就是回文.

[注意事项]

1. 注意区分奇偶数,奇数整体思路没问题,但是偶数永远不会相遇,此时就需要引入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,另一个为Bif(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;//返回交点}
}

整体思路
先让长链表走短链表与长链表的差值步,之后一起走,相遇之后就有交点.

[注意事项]

1. 不确定哪个链表长,哪个链表短,所以长度的差值可能为负数.我们定义长链表和短链表来解决这个问题,利用长度的差值来判断长短.
2. 有一个非常隐形的问题,链表可能不想交,所以我们要用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;}
}

整体思路
定义一个快指针,一个慢指针,快指针一次走两步,慢指针一次走一步,最终进入环的时候必定会相遇.相遇一定就有环.

[注意事项]

1. 首先判断的是链表有没有环,这是循环的条件.
2. 在循环体内部再判断会不会相遇.

动态演示

环形链表

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同时向入口处走,相遇的地方就是要返回的点.

[数学推导]

动态演示

寻找环的入口