每日三题-两数相加、反转链表、回文链表
每日三题-两数相加、反转链表、回文链表
才疏学浅的木子
发布于 2022-11-13 09:29:51
发布于 2022-11-13 09:29:51
代码可运行
运行总次数：0
代码可运行
👨💻个人主页： 才疏学浅的木子 🙇♂️ 本人也在学习阶段如若发现问题，请告知非常感谢 🙇♂️ 📒 本文来自专栏： 算法 🌈 算法类型：Hot100题 🌈
每日三题
两数相加
解法一
使用双指针 每次l1、l2指针都向后移动，但是可能存在一个进位然后保存下来 所以当前值每次都是
(l1.val+l2.val+进位)%10，而进位值就是(l1.val+l2.val+进位 )/10
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 判断一下是否有空的
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode res = new ListNode(0);
ListNode temp = res;
int jin = 0; //进位
while(l1 != null || l2 != null){
int add1 = l1 == null?0:l1.val; // 第一个加数
int add2 = l2 == null?0:l2.val; // 第二个加数
int sum = add1 + add2 + jin; //和
temp.next = new ListNode(sum%10);
temp = temp.next;
jin = sum/10;
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
}
if(jin != 0)temp.next = new ListNode(jin); //最后可能有进位
return res.next;
}
}反转链表
解法一
使用双指针 cur指针指向当前节点，pre指向上一个节点，每次ne临时指针指向下一个节点 cur 指向pre，然后
pre = cur，cur = ne然后继续循环 因为返回条件是cur ！= null，所以返回时候cur是null我们需要返回cur的前一个也就是pre
class Solution {
public ListNode reverseList(ListNode head) {
// 如果为空或者只有一个节点
if(head == null || head.next == null)return head;
ListNode pre = null; // 前一个节点
ListNode cur = head; // 当前节点
while(cur != null){
ListNode ne = cur.next; // 保留下一个节点
cur.next = pre; // 当前节点的下个节点为前一个节点
pre = cur;
cur = ne;
}
return pre;
}
}解法二
使用递归
链表反转，所以最后我们返回的节点就是末尾的那个节点，每次返回末尾节点所以递归完成我们就是返回的最后一个节点
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null)return head; // 递归结束条件
ListNode ne = reverseList(head.next); // 会一直递归找到了5这个节点
head.next.next = head; // 将下个节点的下个节点设置为当前节点
head.next = null; // 当前节点的下个节点设置为null，避免链表成环
return ne;
}
}解法三
循环头插法 每次到插入到res的下一个节点位置
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode res = new ListNode(); // 新的头节点的前一个节点
while(head != null){
ListNode ne = head.next; // 保存当前节点的下一个节点
head.next = res.next; // 当前节点下个节点为res的下个节点
res.next = head; // res的下个节点为当前节点
head = ne; //当前节点为下个节点
}
return res.next;
}
}回文链表
解法一
使用栈 将数据全部压入栈中，因为栈是
先进后出，所以栈中数据相当于反转后的数据 然后栈中数据与链表数据一一比较，如果不一致直接returen false结束
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
Stack<ListNode> s = new Stack<ListNode>();
ListNode p = head;
while(p != null){ // 将链表所有数据压入栈中
s.add(p);
p = p.next;
}
p = head;
while(!s.isEmpty()){ // 比较栈中的值与链表的值是否相等
ListNode t = s.pop();
if(t.val != p.val) return false;
p = p.next;
}
return true;
}
}解法二
链表反转+比较 与上面链表反转类似不再赘述
解法三
快慢指针 + 链表反转 O(n) 时间 O(1) 空间 与解法二类似，只是只反转后部分链表然后比较
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
ListNode s = head;
ListNode q = head.next;
while(q != null && q.next != null){
s = s.next;
q = q.next.next;
}
ListNode t = reverse(s.next); // 反转后半截
while(t != null){
if(t.val != head.val) return false;
head = head.next;
t = t.next;
}
return true;
}
public ListNode reverse(ListNode head){
if(head == null || head.next == null) return head;
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode ne = cur.next;
cur.next = pre;
pre =cur;
cur = ne;
}
return pre;
}
}解法四
使用递归 因为递归相当于帮我们维护一个栈
class Solution {
ListNode t = null;
public boolean isPalindrome(ListNode head) {
if(head == null) return true; // 结束条件
t = head;
return check(head);
}
public boolean check(ListNode head){
if(head == null) return true; // 没有head.next，因为使用head.next那么最后一个不会展示出来
boolean res = check(head.next)&&(t.val == head.val);
t = t.next;
return res;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-11-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
