1. 链表中倒数第K个节点
题目描述:
描述 :
输入一个链表，输出该链表中倒数第k个结点。
示例1 :
输入：1,{1,2,3,4,5}
返回值：{5}
链接：点这里
来源： 牛客网
解题思路：
快慢指针实现 , 定义两个引用变量 fast(快) 和 slow(慢) , 先让 fast 走k-1步 , 走完之后此时 fast 和 slow 再同时走 , 当 fast 走到最后一个节点时 , show 指向的就是 倒数第 k 个节点
代码实现：
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindKthToTail(ListNode head,int k) { if(k <= 0 || head == null) { return null; } ListNode fast = head; ListNode slow = head; //先让fast走k-1步 while(k-1 != 0) { fast = fast.next; if(fast == null) { return null; } k--; } while(fast.next != null) { fast = fast.next; slow = slow.next; } return slow; } }
2. 链表分割(CM11)
题目描述:
描述 :
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
链接：点这里
来源： 牛客网
解题思路：
从前到后逐个按顺序去遍历链表节点 , 将小于x的元素逐个按顺序插入到一个新的链表中 , 同样的将大于x的元素逐个按顺序插入到一个新的链表中 ; 最后将小于x的链表的尾节点和大于x的链表的头节点连接起来组成一个新的链表 , 返回头节点即可 ;
那么如何去实现这两个链表呢 , 我们可以声明两个引用as 和 ae , 用来维护比x大的链表 ; 再声明bs和be来维护比x小的链表 ;
代码中还有几点细节需要注意 , 大于x的链表的最后一个节点相当于合并后链表的尾节点 , 要注意此时尾节点的next不一定为null , 需要去判断并置空 ; 将两个链表合并前要去判断较小的链表是不是空链表 , 是的话直接返回bs .
代码实现：
import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Partition { public ListNode partition(ListNode pHead, int x) { ListNode cur = pHead; //指向比x小的部分 ListNode bs = null; ListNode be = null; //指向比x大的部分 ListNode as = null; ListNode ae = null; //遍历整个链表 while(cur != null) { if(cur.val < x) { //第一次插入节点 if(bs == null) { bs = cur; be = cur; }else { //不是第一次插入节点 be.next = cur; be = be.next; } }else { if(as == null) { as = cur; ae = cur; }else { ae.next = cur; ae = ae.next; } } cur = cur.next; } //判断较小部分是不是空链表 if(be == null) { return as; } //将两段链表连接起来 be.next = as; //将尾节点的next设置为null if(as != null) { ae.next = null; } return bs; } }
提交结果：
3. 链表的回文结构(OR36)
题目描述:
描述 :
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1
返回：true
链接：点这里
来源： 牛客网
解题思路：
判断链表是不是回文结构 , 只需要两个指针 , 一个从前往后 , 另一个从后往前 , 判断每一对元素是不是相等 ;但是单链表只支持从前往后遍历 , 实现不了从后往前的 ; 由此我们就想怎么才能实现将后半段链表元素从后往前遍历呢?
以这里可以去实现将链表的后半段节点反转(反转单链表) , 此时上面的想法就可以实现了 , 后半段的反转需要先找到中间节点(利用快慢指针去实现) ;
要实现这个过程还有很多细节需要注意 , 具体看下面给出的代码 .
代码实现：
import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class PalindromeList { public boolean chkPalindrome(ListNode head) { //判断是否为空列表 if(head == null) { return false; } //只有一个节点时 if(head.next == null){ return true; } //找到中间节点 ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } //将show后半段链表反转 ListNode cur = slow.next; while(cur != null) { //先记录cur的下一个节点位置，否则再反转后会失联 ListNode curNext = cur.next; //更改指向 cur.next = slow; slow = cur; cur = curNext; } //判断回文，此时show相对于原链表在最后一个位置 while(head != slow) { if(head.val != slow.val) { return false; } //处理偶数情况 if(head.next == slow) { return true; } head = head.next; slow = slow.next; } return true; } }
