004 | 线性表面试经典上

写在前面：纸上得来终觉浅，绝知此事要躬行！有人说学数据结构光看不练就是耍牛氓，通过这几天的练习，感觉看跟写真的是两码事，前者是面儿后者才是里。

1. 若某表最常用的操作是在最后一个结点之后插入一个节点或删除最后一二个结点，则采用（）省运算时间。
   A. 单链表
   B. 双链表
   C. 单循环链表
   D. 带头结点的双循环链表
   答案：D
   解析：单链表和双链表每次找到尾部都需要遍历整个链表，单循环链表是单向的，找到尾部也需要遍历整个链表！

2. 构造线性表结点类，下面后续的练习都采用此类：

package link;

/**
 * User: ZhangQi
 * Date: 2019/3/8
 * Time: 9:52
 * Desc: 结点类
 */
public class ListNode {

    //数值域
    int val;
    //指针域
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
    
}

3. 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList

package link;

import java.util.ArrayList;

/**
 * User: ZhangQi
 * Date: 2019/3/8
 * Time: 9:57
 * Desc: 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList
 */
public class Solution {

    /**
     * 思路一：由于需要倒叙输出链表，所以第一时间想到的是反转链表然后在遍历取值
     */
    ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
        if(listNode == null) return list;

        ListNode next = null;
        ListNode pre = null;
        /** 反转链表 */
        while(listNode!=null){
            next = listNode.next;
            listNode.next = pre;
            pre = listNode;
            listNode = next;
        }
        /** 遍历反转后的链表取值 */
        while(pre!=null){
            list.add(pre.val);
            pre = pre.next;
        }
        return list;

    }

    /**
     * 思路2：由于单链表只能从前往后遍历，而需要是需要倒叙链表，也就是先进后出的场景，
     *        而从想到 栈结构 进而想到递归
     * @param listNode
     * @return
     */
    public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
        if(listNode == null) return list;

        /** 使用递归必须要有一个退出条件 */
        if (listNode != null) {
            this.printListFromTailToHead2(listNode.next);
            list.add(listNode.val);
        }
        return list;

    }
    
}

4. 输入一个链表，输出该链表中倒数第k个结点

package link;

/**
 * User: ZhangQi
 * Date: 2019/3/8
 * Time: 9:57
 * Desc: 输入一个链表，输出该链表中倒数第k个结点
 */
public class Solution {

    /**
     * 思路：定义快指针和慢指针，当快指针走到 k-1 步的时候，快，慢指针一起走，
     *       当快指针遍历完链表的时候，慢指针所在到结点就是倒数第k个结点率
     * @param head
     * @param k
     * @return
     */
    public ListNode FindKthToTail(ListNode head, int k) {

        if (head == null || k <= 0) return null;

        /** 初始化快，慢指针，使其指向头指针 */
        ListNode fast = head;
        ListNode show = head;
        
        /** 快指针先走，让其到达 k-1 结点处 */
        while (fast != null && k > 0) {
            fast = fast.next;
            k--;
        }
        /** 快慢一起走，直至快指针遍历完链表 */
        while (fast != null) {
            show = show.next;
            fast = fast.next;
        }
        /** 判断 k 值是否大于链表长度 */
        return k > 0 ? null : show;

    }

}

5. 输入一个链表，反转链表后，输出新链表的表头

package link;

/**
 * User: ZhangQi
 * Date: 2019/3/8
 * Time: 9:57
 * Desc: 输入一个链表，反转链表后，输出新链表的表头
 */
public class Solution {

    /**
     * 思路：反转链表主要是对指针域进行转向操作
     * @param head
     * @return
     */
    public ListNode ReverseList(ListNode head) {

        ListNode newLink = null;
        ListNode next = null;
        while (head != null) {
            /** 记录下一个结点位置，避免遗失 */
            next = head.next;
            /** 反转指针域使其指向上一个结点 */
            head.next = newLink;
            /** 新链表向前进一步，这一步一定要在下一步之前完成 */
            newLink = head;
            /** 最后旧链表指针向前一步进行遍历 */
            head = next;
        }
        return newLink;
    }

}