第二天——链表(简单)

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int[] ReversePrint(ListNode head) {
        Stack<int> tempStack = new Stack<int>();
        while(head!=null)
        {
            tempStack.Push(head.val);
            head = head.next;
        }

        int[] tempArray = new int[tempStack.Count];

        for(int i=0;tempStack.Count!=0;i++)
        {
            tempArray[i] = tempStack.Pop();
        }

        return tempArray;
    }
}

我的思路还是很暴力

用一个栈来装这个链表的数

因为先进后出

所以再用一个数组存放出栈的值就可以了

最后返回这个数组


剑指 Offer 24. 反转链表

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode low = head;
        ListNode high = null;

        while(low != null)
        {
            ListNode temp = low.next;
            low.next = high;
            high = low;
            low = temp;
        }

        return high;
    }
}

使用的算是比较特别的双指针的思路

因为又是没有pre的单向链表

所以不能用以字符串翻转的思路来想这道题

在这个链表最前方添加一个null的节点

然后开始依次进行局部的反转

每次反转完后high和low都向前再移一位

直到最后完成翻转

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注