一、链表中倒数时第k个节点:
1、题目:
输入一个链表,输出该链表中倒数第k个结点。
2、解题思路:单链表具有单向移动的特性。
(1)第一种:先遍历链表,算出链表节点数count,第二次直接遍历到第count-k个节点。但是要注意,可能链表节点数count小于k,此时要返回NULL,所以要先判断这个条件。(这一种就不贴代码出来了)
(2)第二种:
可以用两个指针,一个指针遍历到第k个结点的时候,第二个指针再走到第一个节点,然后两个指针的距离始终保持k-1,这样,当第一个指针的next==NULL,也就是走到最后一个节点的时候,第二个指针对应的位置,就是倒数第k个结点。
这样的好处是能够节省一个循环,时间复杂度会相应降低。从Q(2N) 到Q(N)
注意,但是需要一个小循环让第一个指针先走到第k个指针。同时也存在结点总数小于k的问题,如果循环还没有进行到k次,而第一个指针的已经是NULL,即走到头了,那么,函数返回NULL。
3、代码实现:
/*
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(head ==null || k<=0){
return null;
}
ListNode last=head;
//第一个指针先移动k-1个节点
for(int i=0;i<k-1;i++){
if(head.next!=null){
head=head.next;
}else{
return null;
}
}
//同时移动两个指针,当第一个指针指向null的时候,last就是所求的结点
while(head.next!=null){
head=head.next;
last=last.next;
}
return last;
}
}
二、反转链表:
参考博客:https://www.jianshu.com/p/e385d9c06672
1、题目:
输入一个链表,反转链表后,输出新链表的表头。
2、解题思路:
2-1:第一种:使用递归方式:
(1)解题思路:
假设链表为[1,2,3,4,5]先迭代到链表末尾5,然后从5开始依次反转整个链表。
如下图所示,先迭代待最后一位5,并且设置一个新的节点newList作为反转后链表的头结点,由于整个链表反转后的头就是最后一个数,所以newList存放的一直是反转后的头结点的地址,将head指向的地址赋值给head->next->next指针,并且一定要记得让head->next =NULL,也就是断开现在指针的链接,否则新的链表形成了环,下一层head->next->next赋值的时候会覆盖后续的值。依次反转。。
(2)代码实现:
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
//递归方式
if(head==null || head.next==null){
return head;
}
ListNode newList=ReverseList(head.next);
head.next.next=head;
head.next=null;
return newList;
}
}
2-2第二种:使用迭代方式:
(1)解题思路:
先给定一个空的链表newList,然后判断传入的链表head是不是空链表或者链表元素只有一个,如果是,直接返回就可以。如果不是,则对链表进行迭代,然后给一个临时变量temp存储head.next,然后改变head.next的指向newList,然后把head赋值给newList,接着让head等于临时变量temp,就这样一直迭代完整个链表,返回newList就可以。如下图所示:
(2)代码实现:
public ListNode ReverseList(ListNode head) {
//非递归方式:
ListNode newList=null;
if(head==null || head.next==null){
return head;
}
while(head!=null){
ListNode temp=head.next;
head.next=newList;
newList=head;
head=temp;
}
return newList;
}
三、合并两个排序的链表:
参考博客:https://blog.csdn.net/qq_23217629/article/details/51730312
1、题目:
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
2、解题思路:
比较两个链表的第一个节点,取出最小值的节点,接着再按照相同的方式重复比较剩余链表的节点。
3、代码实现:
public class Solution {
public ListNode Merge1(ListNode list1, ListNode list2) {
//递归版本
ListNode head;
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.val < list2.val) {
head = list1;
head.next = Merge(list1.next, list2);
} else {
head = list2;
head.next = Merge(list1, list2.next);
}
return head;
}
public ListNode Merge(ListNode list1,ListNode list2) {
//非递归版本:
ListNode head = new ListNode(-1);//头节点,用来存储合并的链表
head.next = null;
ListNode root = head;//root暂存我新建的头节点,合并之后返回root.next,就是题目给的头节点
while(list1!=null && list2!=null){
if(list1.val <=list2.val){
head.next=list1;
head = list1;
list1 = list1.next;
}else{
head.next=list2;
head=list2;
list2=list2.next;
}
}
//把未结束的链表连接到合并后的链表尾部
if(list1 !=null){
head.next=list1;
}
if(list2 !=null){
head.next=list2;
}
return root.next;
}
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114699.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...