• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

今天继续LeetCode上的问题,明天准备写最近学的springmvc。

题目一:剑是指在Offer上从末尾到末尾打印链表,即从链表的末尾输出链表,用数组返回。这个想法是利用堆栈的特性来完成的。

ContractedBlock.gif

ExpandedBlockStart.gif

公共类办公室06 {

公共静态void main(String[] args) {

ListNode head=null

//使用尾插入法插入节点,时间复杂度有点高。

for(int I=0;i6;i ){

ListNode listNode=新的ListNode(I);

//判断头节点是否为空,如果是,则为其分配一个node对象,成为头节点。

if(head==null){

head=listNode

}否则{

ListNode cur=head

//从开始节点遍历链表,在最后一个节点挂载新节点。

while (cur.next!=null) {

cur=cur.next

}

cur.next=listNode

}

}

解决方案=新解决方案();

//注意这里不能传入头插入方法的链表,因为头插入方法的头节点发生了变化,据我理解,它的指针指向了屁股。

solution . reverse print(head);

}

}

//节点对象

类别列表节点{

int val

ListNode next

ListNode(int x){

val=x;

}

}

类别解决方案{

//传入链表的头节点

public int[]reverse print(list node head){

stack list node stack=new stack list node();

ListNode temp=head

//将链表的头节点推入堆栈,然后指向下一个节点

while(temp!=null){

stack . push(temp);

temp=temp.next

}

int size=stack . size();

int[]print=new int

//利用堆栈先进后出的特性,将有值的节点对象弹出放入数组,实现链表逆序输出。

for(int I=0;isizei ){

print=stack.pop()。val

system . out . print(print);

}

返回打印;

}

}

查看代码

题目二:剑指Offer上的倒链表,我是按照作者的迭代完成的:jyd论解。

ContractedBlock.gif

ExpandedBlockStart.gif

公共类办公室24 {

public static void main(String[] args) { ListNode01 head=null; //使用尾插法插入结点,时间复杂度有点高 for(int i=0;i<6;i++){ ListNode01 listNode=new ListNode01(i); //判断头结点是否为空,是的话将一个节点对象赋给它,成为头节点 if(head==null){ head=listNode; }else { ListNode01 cur=head; //从头节点开始遍历链表,将新节点挂载到最后一个节点上 while (cur.next != null) { cur = cur.next; } cur.next=listNode; } } Solution01 solution01=new Solution01(); ListNode01 listNode01=solution01.reverseList(head); //从头结点开始输出结点元素 for (int i=0;i<6;i++){ System.out.println(listNode01.val); listNode01=listNode01.next; } } } //节点对象 class ListNode01{ int val; ListNode01 next; ListNode01(int x){ val=x; } } //题目要求为链表的倒序输出,并且之前的头节点指向空 class Solution01 { public ListNode01 reverseList(ListNode01 head) { ListNode01 prev=null; ListNode01 curr=head; while (curr!=null){ //存储当前结点的下个结点,为中间变量 ListNode01 temp=curr.next; //将当前结点的下个结点变成它的前一个结点,如果没有则为空 curr.next=prev; //prev是存储当前结点,为下一次循环做准备 prev=curr; //将当前结点变成下个结点,即将指向倒过来,当到链表的最后一个元素时,temp必定为null退出循环 curr=temp; } return prev; } } View Code

题目三:复杂链表的复制,同样借鉴LeetCode作者:jyd,这个是利用HashMap中键值对的映射关系来完成

ContractedBlock.gifExpandedBlockStart.gif
public class Office35 {
    public static void main(String[] args) {
        Node head=null;
        //使用尾插法插入结点,时间复杂度有点高
        for(int i=0;i<6;i++){
            Node listNode=new  Node(i);
            //判断头结点是否为空,是的话将一个节点对象赋给它,成为头节点
            if(head==null){
                head=listNode;
            }else {
                Node cur=head;
                //从头节点开始遍历链表,将新节点挂载到最后一个节点上
                while (cur.next != null) {
                    cur = cur.next;
                }
                cur.next=listNode;
                cur.next.random=cur;
            }
        }
        Solution02 solution02=new Solution02();
        Node node=solution02.copyRandomList(head);
        while (node!=null){
            //输出该结点的值和该结点指向结点的值
            if(node.random!=null) {
                System.out.println("结点的值:"+node.val + " " + "结点的random指针"+node.random.val);
            }
            node=node.next;
        }
    }
}
class Node{
    int val;
    Node next;
    //random是一个指向其他结点的指针
    Node random;
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
class Solution02 {
    //这个算法的复制原理就是利用hashmap的key和value的映射关系,完成复制
    //先创建一个结点,将一个结点的val给它,然后利用hashmap创建映射关系
    //再将链表的的指向给复制链表
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        Node cur=head;
        //利用hashmap的键值对的映射关系完成原链表与复制链表的映射关系
        Map<Node,Node> map=new HashMap<>();
        while (cur!=null){
            //创建映射关系
            map.put(cur,new Node((cur.val)));
            cur=cur.next;
        }
        //重新指向头结点
        cur=head;
        while (cur!=null){
            //将原链表的下一个结点指向赋值给赋值链表,map.get(key)是根据传入的key值取出相应的value值
            map.get(cur).next=map.get(cur.next);
            //将原链表的random赋值给复制链表
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        //返回复制链表的头结点
        return map.get(head);
    }
}
View Code

 

Link to comment
Share on other sites