大家好,我是bug郭,一名双非科班的在校大学生。对C/JAVA、数据结构、Spring系列框架、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流

作者简介:

• CSDN java领域新星创作者blog.csdn.net/bug…
• 掘金LV3用户 juejin.cn/user/bug…
• 阿里云社区专家博主,星级博主,developer.aliyun.com/bug…
• 华为云云享专家 bbs.huaweicloud.com/bug…

从尾到头打印链表

题目链接:从头到尾打印链表信息

题目分析:

• 直接遍历借助栈数据结构先进先出

题目解答:

空间/时间复杂度:O(n)

java

import java.util.*;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        if(listNode==null||listNode.next==null) return res;
        while(listNode!=null){ //栈保存
            stack.add(listNode.val);
            listNode = listNode.next;
        }
        while(!stack.isEmpty()){//然后出栈!
            res.add(stack.pop());
        }
        return res;
    }
}

python

class Solution:
    def printListFromTailToHead(self , listNode: ListNode) -> List[int]:
        # write code here
        res = []
        cur = listNode
        while cur != None:
            res.insert(0,cur.val)
            cur = cur.next
        return res

• 我们可以这里关键点就是需要知道当前节点上一个节点的位置!
• 这里我们可以通过递归,可以达到和栈一样的效果!

复杂度和上面一样,就是通过递归栈代替了我们自定义的栈!

java

import java.util.ArrayList;
public class Solution {
     ArrayList<Integer> res;
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //递归!!!
       res = new ArrayList<>();
        dfs(listNode);
        return res;
    }
    public void dfs(ListNode cur){
        if(cur==null) return;
        dfs(cur.next);//找尾!
        res.add(cur.val);
    }

}

python

import sys
sys.setrecursionlimit(100000) # 设置递归深度!

class Solution:
    def dfs(self,cur: ListNode, res: List[int]):
        if cur is None:
            return
        self.dfs(cur.next,res)
        res.append(cur.val)

    def printListFromTailToHead(self, listNode: ListNode) -> List[int]:
        # write code here
        res = []
        self.dfs(listNode, res)
        return res

反转链表

题目链接:反转链表

题目分析:

• 这里空间复杂度为O(1)那就要求原地反转链表!
• 显然这里不能借助其他数据结果,或者递归!
• 所以我们可以通过多个指针记录反转节点位置进行操作

java

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null,cur = head,end = head;
        while(end!=null){
            end = cur.next;
            cur.next = pre;
            pre = cur;
            cur = end;
        }
        return pre;
    }
}

python

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        # write code here
        pre,cur,end = None,head,head
        while cur != None:
            end = cur.next
            cur.next = pre
            pre = cur
            cur = end
        return pre

合并两个排序的链表

题目链接:合并两个排序的链表

题目分析:

• 这里是2个排序链表!
• 我们可以创建一个新链表,然后遍历这2个链表,比较2个链表中的元素!
• 较小值就尾插到新链表!
• 返回新链表即可
• 注意比较时有可能有链表已经为空,所以直接尾插另一个链表即可!

java

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode cur1 = list1,cur2 = list2;
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while(cur1!=null&&cur2!=null){
            if(cur1.val<cur2.val){
                cur.next = cur1;
                cur1 = cur1.next; 
            }else{
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
		if(cur1!=null){
			cur.next = cur1;
		}
		if(cur2!=null){
			cur.next = cur2;
		}
		return cur;
}

python

class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        dummy = ListNode(-1)
        cur = dummy
        while pHead1 and pHead2:
            if pHead1.val<pHead2.val:
                cur.next = pHead1
                pHead1 = pHead1.next
            else:
                cur.next = pHead2
                pHead2 = pHead2.next
            cur = cur.next
 		if pHead1:
            cur.next = pHead1
        if pHead2:
            cur.next = pHead2
        return dummy.next