数据结构学习笔记（三续）：单链表常见面试题

一、查找单链表中倒数第K个节点

​ 思路：先找出单链表中有效节点的个数length，再通过length-K找到倒数第K个节点，但是要注意头节点不算在内。

//获取链表中有效节点的个数
    public int getLen(HeroNode hero){
        HeroNode temp = head.next;
        int length = 0;
        if (temp == null){
            return 0;
        }
        while (temp != null){
            length++;
            temp = temp.next;
        }
        return length;
    }

//获取节点中倒数第K个值
    public HeroNode findLastKNode(HeroNode head,int k){
        HeroNode temp = head.next;
        if (temp == null){
            return null;
        }
        if (k<0 || k>getLen(head)){
            System.out.println("超出链表范围");
        }
        for (int i = 0; i < getLen(head) - k; i++) {
            temp = temp.next;
        }
        return temp;
    }

二、反转单链表

​ 思路：首先创建一个新的链表头部reverseHaed。并且创建两个临时变量cur,next来储存节点，遍历整个链表。

​

​ 第一步，将第一个节点指向reverseHead.next,然后再将reverseHead.next指向第一个节点，这样就把第一个节点拿了下来；

​ 第二步同第一步，将第二个节点指向reverseHead.next即原来的第一个节点，再将reverseHead.next指向第二个节点，这样第二个节点也拿了下来。

​ 以此类推，当所有节点拿下来之后，将原先的头指针指向最后拿下的第一个节点，完成单链表的反转。

​

​ 实现代码：

public void reverseNord(HeroNode head){
        HeroNode cur = head.next;
        HeroNode next = null;
        HeroNode reverseHead = new HeroNode(0,"","");
        if (cur == null || cur.next == null){
            return;
        }
        while (cur != null){
            next = cur.next;
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            cur = next;
        }
        head.next = reverseHead.next;
    }

三、从尾到头打印链表

​ 方式1：先将单链表进行反转操作，然后遍历即可；

​ 但是这样会破坏原来的单链表的结构，不可取。

​ 方式2：利用栈这个数据结构，将各个节点压入栈中，利用栈的先进后出的特点即可实现逆序打印。

    public void reversePrint(HeroNode head){
        if (head.next == null){
            return;
        }
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode cur = head.next;
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }

四、按顺序合并两个链表（递归）

public class NodeList(){
    int data;
    NodeList next;

    NodeList(int num){
        data = num;
    }
}  

public class margeTwoLists{
    public NodeList margeTwoLists(NodeList haed1,NodeList head2){
        if(head1 == null){
            return head2;
        }    
        if(head2 == null){
            return head1;
        }

        NodeList head = null;
        while(head1 !=null && head2 !=null){
            if(head1 => head2){
                head = head2;
                head.next = margeTwoLists(head1,head2.next)
            }else{
                head = head1;
                head.next = margeTwoLists(head2,head1.next)
            }
        }
        return head;
    }
}