剑指offer:22-25记录
【摘要】 输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
示例:
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
思路:快指...
输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
示例:
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
思路:快指针先走k步,然后快慢指针一起走到快指针到头为止,这时慢指针就是答案。
-
/**
-
* Definition for singly-linked list.
-
* public class ListNode {
-
* int val;
-
* ListNode next;
-
* ListNode(int x) { val = x; }
-
* }
-
*/
-
class Solution {
-
public ListNode getKthFromEnd(ListNode head, int k) {
-
ListNode former = head, latter = head;
-
for(int i = 0; i < k; i++)
-
former = former.next;
-
while(former != null) {
-
former = former.next;
-
latter = latter.next;
-
}
-
return latter;
-
}
-
}
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制:
0 <= 节点个数 <= 5000
-
/**
-
* Definition for singly-linked list.
-
* public class ListNode {
-
* int val;
-
* ListNode next;
-
* ListNode(int x) { val = x; }
-
* }
-
*/
-
class Solution {
-
public ListNode reverseList(ListNode head) {
-
//前一个节点
-
ListNode pre = null;
-
//当前处理节点
-
ListNode cur = head;
-
//记录后一个节点用
-
ListNode tmp = null;
-
-
while(cur!=null) {
-
//记录当前节点的下一个节点
-
tmp = cur.next;
-
//然后将当前节点指向pre
-
cur.next = pre;
-
//pre和cur节点都前进一位
-
pre = cur;
-
cur = tmp;
-
}
-
return pre;
-
}
-
}
输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
限制:
0 <= 链表长度 <= 1000
思路:链表的一次归并。思路和数组类似。
-
/**
-
* Definition for singly-linked list.
-
* public class ListNode {
-
* int val;
-
* ListNode next;
-
* ListNode(int x) { val = x; }
-
* }
-
*/
-
class Solution {
-
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
-
ListNode ans=new ListNode(-1);
-
ListNode temp=ans;
-
while(l1!=null && l2!=null){
-
if(l1.val>l2.val){
-
ans.next=l2;
-
l2=l2.next;
-
}else{
-
ans.next=l1;
-
l1=l1.next;
-
}
-
ans=ans.next;
-
}
-
if(l1!=null)ans.next=l1;
-
if(l2!=null)ans.next=l2;
-
return temp.next;
-
}
-
}
文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。
原文链接:fantianzuo.blog.csdn.net/article/details/104758590
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)