广州专业做外贸网站建设,视频怎么下载,如何设计一个网站页面,重庆建设集团网站206. 反转链表 - 力扣#xff08;LeetCode#xff09;
1. 题目描述
给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。
示例1 输入#xff1a;head [1,2,3,4,5] 输出#xff1a;[5,4,3,2,1] 示例2 输入#xff1a;head [1,2] 输出LeetCode
1. 题目描述
给你单链表的头节点 head 请你反转链表并返回反转后的链表。
示例1 输入head [1,2,3,4,5] 输出[5,4,3,2,1] 示例2 输入head [1,2] 输出[2,1] 示例3 输入head [ ] 输出[ ] 提示
链表中节点的数目范围是[0,500]-5000 Node.val 5000
2. 思路 判断链表是否为空如果为空直接返回头结点 判断链表是否为一个元素如果是直接返回头结点 将head置为null 定义两个指针cur和curNextcur 指向头结点的next表示要反转的元素curNext指向cur的next表示要反转元素的下一个元素 使用头插法将要反转的元素插入前一个元素的前面
3.代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {if (head null) { // 链表里一个元素都没有return head;}if (head.next null) { // 链表里只有一个元素return head;}ListNode cur head.next; // 要反转的元素head.next null;while (cur ! null) {ListNode curNext cur.next;// 头插法cur.next head;head cur;cur curNext;}return head;}
}运行结果 876. 链表的中间结点 - 力扣LeetCode
1.题目描述
给你单链表的头结点 head 请你找出并返回链表的中间结点。
如果有两个中间结点则返回第二个中间结点。
示例1 输入head [1,2,3,4,5] 输出[3,4,5] 解释链表只有一个中间节点值为3 示例2 输入head [1,2,3,4,5,6] 输出[4,5,6] 解释链表只有两个中间节点值分别为3和4返回第二个节点。 提示
链表的节点的范围是[1,100]1 Node.val 100
2. 思路
判断头结点的next是否为空如果是直接返回头结点定义两个指针slow和fast都指向头结点。循环遍历链表每次fast指向fast的next的next每次移动两步slow指向slow的next每次移动1步循环条件fast null循环结束链表元素个数为偶数时fast.next null循环结束链表元素个数为奇数时。 3.代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode middleNode(ListNode head) {if (head.next null) {return head;}ListNode slow head;ListNode fast head;while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;}return slow;}
}运行结果 链表中倒数第k个结点
1. 题目描述
输入一个链表输出该链表中倒数第k个结点。
示例1 输入1,{1,2,3,4,5} 返回值{5} 2. 思路
判断k是否合法如果不合法直接返回null。判断链表是否为空如果为空直接返回null。定义两个指针fast和slow都是指向头结点。让fast先走k-1步。在让fast和slow同时走当fast.next null都走到了链表最后一个节点了同时slow也走到了倒数第K个节点 3.代码
import java.util.*;
/*
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) { // k为负数return null;}if (head null){return null;}ListNode fast head;ListNode slow head;int count 0;while (count ! (k - 1)) {if (fast.next ! null) {fast fast.next;count;} else { // k 大于链表长度return null;}}while (fast.next ! null) {fast fast.next;slow slow.next;}return slow;}
}
运行结果 21. 合并两个有序链表 - 力扣LeetCode
1. 题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例1 输入l1 [1,2,4] l2 [1,3,4] 输出[1,1,2,3,4,4] 示例2 输入l1 [] l2 [] 输出[] 示例3 输入l1 [] l2 [0] 输出[0] 2.思路
创建一个节点newHead为虚拟节点开始比较链表的大小谁大newHead就指向谁头结点就指向头结点的next判断链表是否为空为空则newHead指向头结点的next 3. 代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode newHead new ListNode(-1);ListNode temp newHead;while(list1 ! null list2 ! null) {if (list1.val list2.val) {temp.next list1;list1 list1.next;temp temp.next;} else {temp.next list2;list2 list2.next;temp temp.next;}}if (list1 ! null) {temp.next list1;}if (list2 ! null) {temp.next list2;}return newHead.next;}
}运行结果
