package com.example.java;

import java.util.ArrayList;
import java.util.Stack;

public class Sort {

    public static void main(String[] args) {
        int[] a = {1, 7, 9, 11, 13, 15, 17, 19};
        int[] b = {2, 4, 6, 7, 10};
        //调用printArray方法，并将merge方法的返回值传给printArray
        printArray(merge(a, b));
    }

    //1. 将两个有序数组合并为一个
    public static int[] merge(int[] a, int[] b) {

        int[] c = new int[a.length + b.length];
        //i用于标记数组a
        int i = 0;
        //j用于标记数组b
        int j = 0;
        //用于标记数组c
        int k = 0;

        //a，b数组都有元素时
        while (i < a.length && j < b.length) {
            if (a[i] < b[j]) {
                c[k++] = a[i++];
            } else {
                c[k++] = b[j++];
            }
        }

        //若a有剩余
        while (i < a.length) {
            c[k++] = a[i++];
        }

        //若b有剩余
        while (j < b.length) {
            c[k++] = b[j++];
        }

        return c;
    }

    //打印数组
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + "  ");
        }
    }


    //2.从链尾打印链表
    public class Solution {
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            ArrayList<Integer> list = new ArrayList<Integer>();
            if (null == listNode) {
                return list;
            }
            Stack<Integer> stack = new Stack<Integer>();
            while (listNode != null) {
                stack.push(listNode.val);
                listNode = listNode.next;
            }
            while (!stack.empty()) {
                list.add(stack.pop());
            }
            return list;
        }
    }

    //3.反转链表
    public ListNode ReverseList(ListNode head) {
        if (head == null)
            return null;
        //head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null；
        ListNode pre = null;
        ListNode next = null;
        //当前节点是head，pre为当前节点的前一节点，next为当前节点的下一节点
        //需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2
        //即pre让head节点可以反转所指方向，但反转之后如果不用next节点保存next1节点的话，此单链表就此断开了
        //所以需要用到pre和next两个节点
        //1->2->3->4->5
        //1<-2<-3 4->5
        while (head != null) {
            //做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
            //如此就可以做到反转链表的效果
            //先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
            next = head.next;
            //保存完next，就可以让head从指向next变成指向pre了，代码如下
            head.next = pre;
            //head指向pre后，就继续依次反转下一个节点
            //让pre，head，next依次向后移动一个节点，继续下一次的指针反转
            pre = head;
            head = next;
        }
        //如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
        //直接输出pre就是我们想要得到的反转后的链表
        return pre;
    }
}


   //4.链表倒数第k个节点
public ListNode FindKthToTail(ListNode head, int k) {
        ListNode pre = head;
        ListNode p = head;
        //记录k值
        int a = k;
        //记录节点的个数
        int count = 0;
        //p指针先跑，并且记录节点数，当p指针跑了k-1个节点后，pre指针开始跑，
        //当p指针跑到最后时，pre所指指针就是倒数第k个节点
        while (p != null) {
            p = p.next;
            count++;
            if (k < 1) {
                pre = pre.next;
            }
            k--;
        }
        //如果节点个数小于所求的倒数第k个节点，则返回空
        if (count < a) return null;
        return pre;
    }