[数据结构与算法]数据结构笔记-单链表面试题

单链表常见面试题

1. 求单链表中节点的个数–遍历就行
2. 查找单链表中倒数第k个节点–新浪面试题
3. 单链表的反转-腾讯面试题
4. 从尾到头打印单链表-百度面试题，要求方法：1）反向遍历；2）Stack栈

面试题1-查找单链表中倒数第k个节点

最简单直接的一个思路：双指针，一个指针先走k步，再将两个指针同时移动；当前一个指针移到最后，则后一个指针.next即为倒数第k个节点

参考力扣题目：删除链表倒数第N个节点

面试题2-反转单链表

参考力扣题目：反转链表
思路：遍历+头插法
需要注意的是力扣给的链表没有韩老师说的无数据头节点，将cur指向head，最后返回reveseHead之后的链表数据即可

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode reverseHead = new ListNode();
        ListNode cur = head;
        ListNode next  = null; //指向当前节点的下一个节点
        while(cur!=null){
            next = cur.next;
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            cur = next;
        }
        //head.next = reverseHead.next;
        return reverseHead.next;
    }
}

面试题3-从尾到头打印链表

思路1：反转+遍历输出
存在一个问题：会破坏原来单链表的结构
思路2：使用栈，将各个节点压入栈内，利用栈先进后出的特点实现逆序打印

个人觉得直接扫描一遍链表，再利用数组反向输出就行
参考力扣题目

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode temp = head;
        int count = 0;
        while(temp != null){
            count++;
            temp = temp.next;
        }
        int [] reverseArr = new int[count];
        temp = head;
        for(int i=count-1; i>=0; i--){
            reverseArr[i] = temp.val;
            temp = temp.next;
        }
        return reverseArr;
    }
}