每日牛客刷题之链表

发布时间:2022-12-13 14:00

✅作者简介:我是18shou,一名即将秋招的java实习生

✨个人主页:_18shou

系列专栏:牛客刷题专栏

推荐一款模拟面试、刷题神器 在线刷题面经模拟面试

目录

看题1之反转链表

思路1

代码1

复杂度1

思路2

代码2

复杂度2

题目2之链表从尾到头返回

思路2.1

代码2.1

复杂度2.1

思路2.2

代码2.2

​编辑

结语


每日牛客刷题之链表_第1张图片

 

看题1之反转链表

给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。
数据范围:0≤n ≤1000
要求:空间复杂度O(1),时间复杂度O(n)。
如当输入链表{1,2,3}时,
经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1]。以上转换过程如下图所示:

思路1

在遍历链表的同时  修改next指向 

代码1

public ListNode ReverseList(ListNode head) {
        ListNode tmp = null;
        while(head != null) {
            ListNode node = head.next;
            head.next = tmp;
            tmp = head;
            head = node;
        }
        return tmp;
    }

复杂度1

时间复杂度O(N):遍历链表使用线性大小时间。
空间复杂度O(1):变量tmp和head使用常数大小额外空间。

 

思路2

考虑使用递归法遍历链表,当越过尾节点后终止递归,在回溯时修改各节点的 next引用指向。
recur(cur,pre)递归函数:
1.终止条件:当cur为空,则返回尾节点pre(即反转链表的头节点);⒉.递归后继节点,记录返回值(即反转链表的头节点)为res ;
3.修改当前节点cur 引用指向前驱节点pre ;
4.返回反转链表的头节点res ;
reverseList(head)函数:
调用并返回recur(head,null)。传入null是因为反转链表后,head节点指向null ;

代码2

class Solution {
    public ListNode reverseList(ListNode head) {
        return recur(head, null);    // 调用递归并返回
    }
    private ListNode recur(ListNode cur, ListNode pre) {
        if (cur == null) return pre; // 终止条件
        ListNode res = recur(cur.next, cur);  // 递归后继节点
        cur.next = pre;              // 修改节点引用指向
        return res;                  // 返回反转链表的头节点
    }
}

复杂度2

时间复杂度O(N) :遍历链表使用线性大小时间。
空间复杂度O(N):遍历链表的递归深度达到N,系统使用O(N)大小额外空间。

每日牛客刷题之链表_第2张图片

 

题目2之链表从尾到头返回

输入一个链表的头节点,按链表从尾到头的顺序返回每个节点的值

每日牛客刷题之链表_第3张图片

 

思路2.1

将链表反转 然后遍历存入List输出  (最笨的方法)

代码2.1

import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList printListFromTailToHead(ListNode listNode) {
        if(listNode == null) {
            return new ArrayList();
        }
        ListNode node = ReverseList(listNode);
        ArrayList list = new ArrayList();
        while(node != null) {
            list.add(node.val);
            node = node.next;
        }
        return list;
        
    }
   public ListNode ReverseList(ListNode head) {
        ListNode tmp = null;
        while(head != null) {
            ListNode node = head.next;
            head.next = tmp;
            tmp = head;
            head = node;
        }
        return tmp;
    }
}

复杂度2.1

每日牛客刷题之链表_第4张图片

思路2.2


栈的特点是后进先出,即最后压入栈的元素最先弹出。考虑到栈的这一特点,使用栈将链表元素顺序倒置。从链表的头节点开始,依次将每个节点压入栈内,然后依次弹出栈内的元素并存储到数组中。·创建一个栈,用于存储链表的节点
·创建一个指针,初始时指向链表的头节点·当指针指向的元素非空时,重复下列操作:
。将指针指向的节点压入栈内
。将指针移到当前节点的下一个节点
·获得栈的大小size,创建一个集合print,其大小为size
·重复size 次下列操作:
。从栈内弹出一个节点,将该节点的值存到list
·返回print

代码2.2

 

import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList printListFromTailToHead(ListNode listNode) {
        Stack stack = new Stack();
        ListNode temp = listNode;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        ArrayList print = new ArrayList(size);
        for (int i = 0; i < size; i++) {
            print.add(stack.pop().val);
        }
        return print;
    }
}

每日牛客刷题之链表_第5张图片

 

结语

兄弟们,一起来刷题嘎嘎的写题

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号