栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode-从尾到头打印链表、反转链表和复杂链表的复制

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode-从尾到头打印链表、反转链表和复杂链表的复制

这是什么?

记录一下每道leetcode我的理解,解题思路。方便以后复习

Day02简单:剑指 Offer 06. 从尾到头打印链表

题目:

思路:看到反转,我首先想到了用栈,最后进来的先出去。遍历链表,从头结点开始压入栈直到末尾节点,最后得到的栈,根据其中元素的个数,全部弹出,用一个int数组按顺序接收即可。

代码:

package lapTop.LeetCode.Day04;


import java.util.ArrayDeque;
import java.util.Deque;

class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }
class Solution {
    public int[] reversePrint(ListNode head) {
        Deque stack = new ArrayDeque<>();
//        int length=0;

        while(head!=null){
            stack.push(head.val);
            head = head.next;
//            length++;
        }

        int length = stack.size();
        int[] res= new int[length];

        for(int i=0;i
            res[i] = stack.pop();
        }
        return res;
    }
}

想法:与官方答案基本一致。

Day02简单:剑指 Offer 24. 反转链表

题目:

思路:尝试用栈,但是没解决。看到题解才知道用的是迭代,也可以用递归,不过使用递归空间开销太大,而且也更加复杂。反转链表要知道当前结点的前一个结点和后一个结点。前一个(prev)结点没办法直接指向,所以在最开始的head结点,prev结点手动指向null,在后面的遍历中再把prev往后移动。后一个结点就可以直接用.next指向。

获取到下一个结点:ListNode next = curr.next;这一步一定要在改变指向之前完成。获取到当前结点,把当前结点的下一个指向改为prev,即curr.next=prev。然后就完成了当前结点指向的改变!接下来只需要将我们的prev和curr往后移动,改变指向,诸如此类。一直到curr的值为空的时候,我们就不需要改变了,因为让null指向某个结点是没有意义的。注意:用while循环判断到curr是null时结束循环,此时prev就是我们要的反转后的头结点,所以最后返回的是prev!

代码:

package lapTop.LeetCode.Day04;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class Solution1 {
    
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while(curr!=null){
            ListNode next = curr.next;//先把当前下一个目标存储起来
            curr.next = prev;
            //整体向后移动
            prev = curr;
            curr = next;
        }
        return prev;
    }

}

想法:自己没做出来,但是学到了迭代的思想。

Day02中等:剑指 Offer 35. 复杂链表的复制

题目:

思路:本题有两种思路:使用递归或者是结点拆分,递归比较好理解,但是我选择节点拆分,因为递归占用空间较大。思路是复制结点,使原结点的下一个指向新结点,新结点的下一个指向原结点的下一个。即从A-B-C-D变成了A-A’-B-B’-C-C’-D-D’。

第一步:遍历所有原结点,使原结点指向复制出来的新结点。这样就新建出了所有的新节点,下一步就可以开始处理random了(如果新结点还没有完全创建的情况下,可能会出现新结点的random指向的新结点还没创建出来,结果使random指向了null)。

第二步:处理新结点的random指针,使其指向原结点的random指针的复制结点。这一步很重要,这一步一定要在处理新结点的next指针前完成,因为我们还要借助A-A’-B-B’-C-C’-D-D’这种指向关系去寻找新的random结点位置。需要注意的是:我们要额外判断原结点random指针指向的是否是null,因为null可没有next指针。

在第二步和第三步之间,我们用一个newHead储存新链表的头结点,Node newHead = head.next;

第三步:处理新结点的next指针。这一步断开新结点和原结点之间的联系,使其关系变为:A-B-C-D和A’-B’-C’-D’。做法非常基础,就是修改next的指向关系,(node是原结点,newNode是新结点)node.next = newNode.next;

newNode.next = newNode.next.next;但是修改newNode的next指向时要注意,newNode的next可能是null,要单独判断,所以修改成:

newNode.next = (newNode.next != null)? newNode.next.next : null;

代码:

package lapTop.LeetCode.Day04;
class Solution2 {

// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }

        for (Node node = head; node != null; node = node.next.next) {
            Node next = node.next;
            node.next = new Node(node.val);
            node.next.next = next;
        }

        for(Node node = head;node != null;node = node.next.next){
            node.next.random = (node.random != null)?node.random.next : null;
        }

        Node newHead = head.next;
        for(Node node = head;node != null;node = node.next){
            Node newNode = node.next;
            node.next = newNode.next;
            newNode.next = (newNode.next != null)? newNode.next.next : null;
        }

        return newHead;
    }
}

想法:妙啊!真是活到老学到老。在递归的解法中使用map集合储存新结点,在结点拆分中利用新旧结点之间的连接关系,直接省去创建map集合的空间。
node.next = newNode.next;
newNode.next = (newNode.next != null)? newNode.next.next : null;
}

    return newHead;
}

}


想法:妙啊!真是活到老学到老。在递归的解法中使用map集合储存新结点,在结点拆分中利用新旧结点之间的连接关系,直接省去创建map集合的空间。
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/978583.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号