每日牛客刷题之链表

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

✨个人主页：_18shou

系列专栏：牛客刷题专栏

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

目录

看题1之反转链表

思路1

代码1

复杂度1

思路2

代码2

复杂度2

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

思路2.1

代码2.1

复杂度2.1

思路2.2

代码2.2

​编辑

结语

看题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.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

思路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;
    }
}

结语

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