【剑指offer 02day】

难度 : 简单

题目 : 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）

示例 ：

输入：head = [1,3,2]
输出：[2,3,1]

提示：

限制：

0 <= 链表长度 <= 10000

大致思路 :

C语言的实现思路 : 因为C语言没有内库函数可用，很多东西要自己写，所以操作起来会比较麻烦。先遍历链表, 通过统计链表的长度, 再定义一个和链表一样的长度的数组， 然后又遍历一遍链表， 主要是读取链表值，从数组末尾开始赋值， 这样数组的值和链表的值的顺序就相反了。

实现语言 : Java

官方做法之一 : 使用辅助栈

class Solution {
    public int[] reversePrint(ListNode head) {
        Stack stk = new Stack();
        ListNode p = head;
        int size = 0;
        while (p != null) {
            stk.push(p.val);
            size ++;
            p = p.next;
        }
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = stk.pop();
        }
        return res;
    }
}

做法二使用递归, 但效率比较低

class Solution {
    private ArrayList res = new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        if (head != null) {
            reversePrint(head.next);
            res.add(head.val);
        }
        return res.stream().mapToInt(i -> i).toArray();
    }
}

实现语言 : C语言

遍历两遍链表
个人实现 :

int* reversePrint(struct ListNode* head, int* returnSize){
    int n = 0;
    struct ListNode *L = head;
    while(L){
        L = L ->next;
        n++;
    }
    int* arr = (int*)malloc(sizeof(int)*n); //分配数组的内存大小
    L = head;
    *returnSize= n;
    while(L){
        arr[n-1] = L->val;
        L = L ->next;    
        --n;
    }
    
    return arr;
}

难度 : 简单

题目 : 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例 ：

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

提示：

限制

0 <= 节点个数 <= 5000

大致思路 :

先遍历一遍链表, 每读取到一个数值使用头插法(即每次元素都将插入在头部位置)将其插入到新链表中, 最后返回一个新链表.

实现语言 : C语言

个人做法 :

typedef struct ListNode LNode;

struct ListNode* reverseList(struct ListNode* head){
    //使用头插法
    LNode* q = (LNode*)malloc(sizeof(LNode));
    q->next = NULL;  //即头结点
    while(head){
        struct ListNode* t = (LNode*)malloc(sizeof(LNode));
        t->val =head->val;
        t->next = q->next;
        q->next = t; 
        head = head->next;
    }
    q = q->next;  //删除第一个结点, 也就是头结点
    return q;
}

官方做法:

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr) {
        struct ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

说明 :

迭代法
假设链表为 1 → 2 → 3 → ∅ 1 rightarrow 2 rightarrow 3 rightarrow varnothing 1→2→3→∅，我们想要把它改成 ∅ ← 1 ← 2 ← 3 varnothing leftarrow 1 leftarrow 2 leftarrow 3 ∅←1←2←3

在遍历链表时，将当前节点的 next textit{next} next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

复杂度分析

• 时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是链表的长度。需要遍历链表一次。
• 空间复杂度： O ( 1 ) O(1) O(1)。