剑指offer题目详细版本（1）

2021-08-18 17:35:53

一、链表题目

1、从尾到头打印链表

使用栈（也可以使用数组，逆序输出）

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        Stack<ListNode> stack = new Stack<>();
        while(listNode!=null){
            stack.push(listNode);
            listNode = listNode.next;
        }
        
        while(!stack.isEmpty()){
            list.add(stack.pop().val);
        }
        return list;
        
    }
}

反转链表再打印

关键点：要注意画图

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
         ArrayList<Integer> list = new ArrayList<>();
        ListNode pre = null;   // 定义前驱节点
        ListNode cur = listNode; // 定义当前节点 
        
        while(cur!=null){
            ListNode next = cur.next;  // 定义后继节点
            cur.next = pre;   
            pre = cur;
            cur = next;
        }
        
        ListNode head = pre;
        while(head!=null){
            list.add(head.val);
            head = head.next;
        }
        
        return list;
    }
}

递归打印链表

递归到链表的尾部，再依次将链表结点存入数组中

算法实现：

变量：先创建一个list数组

递归结束条件：当链表结点为null，listNode==null。

结果：list即为逆序排列链表数值后的数组

剑指offer题目详细版本（1）

import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode!=null){
            printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
        return list;
    }
}

2、反转链表

通过三个指针轮流交替的迭代方法

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

迭代方法

剑指offer题目详细版本（1）

/**
     *递归实现单链表反转
     * @param list 为传入的单链表
     */
    public static Node recursiveList(Node list){
        // 如果链表为空 或者 链表中只有一个节点,直接返回
        // 也是递归结束的条件
        if (list == null || list.next == null) return list;
        Node recursive = recursiveList(list.next);
        // 将 list.next.next 指针指向当前链表 list
        list.next.next = list ;
        // 将 list.next 指针指向 null
        list.next = null;
        // 返回反转之后的链表 recursive
        return recursive;
    }

3、合并两个排序的链表

非递归版本

码农公寓

一、链表题目

1、从尾到头打印链表

2、反转链表

3、合并两个排序的链表

相关文章