面试题22：链表中倒数第k个结点

题目：输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。

public ListNode getKthFromEnd(ListNode head, int k) {
    if (head == null || k <= 0) {
        return null;
    }

    ListNode ahead = head;
    for (int i = 0; i < k - 1; i++) {
        if (ahead.next != null) {
            ahead = ahead.next;
        } else {
            return null;
        }
    }

    ListNode behind = head;
    while (ahead.next != null) {
        ahead = ahead.next;
        behind = behind.next;
    }
    return behind;
}

面试题23：链表中环的入口结点

题目：一个链表中包含环，如何找出环的入口结点？例如，在图3.8的链表中，环的入口结点是结点3。

  • 算法
    • 1.使用快慢指针找到环中任一结点
    • 2.计算环中结点数量
    • 3.以环中结点数量为间距使用前后指针找到环的入口结点 
public ListNode entryNodeOfLoop(ListNode head) {
    ListNode meetNode = meetNode(head);
    if (meetNode == null) {
        return null;
    }

    int nodesInLoop = 1;
    ListNode ahead = meetNode;
    while (ahead.next != meetNode) {
        nodesInLoop++;
        ahead = ahead.next;
    }

    ahead = head;
    ListNode behind = head;
    for (int i = 0; i < nodesInLoop; i++) {
        ahead = ahead.next;
    }
    while (ahead != behind) {
        ahead = ahead.next;
        behind = behind.next;
    }
    return ahead;
}
private ListNode meetNode(ListNode head) {
    if (head == null) {
        return null;
    }

    ListNode slow = head.next;
    if (slow == null) {
        return null;
    }
    ListNode fast = slow.next;
    while (fast != null) {
        if (slow == fast) {
            return slow;
        }
        slow = slow.next;
        fast = fast.next;
        if (fast != null) {
            fast = fast.next;
        }
    }
    return null;
}

面试题24：反转链表

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

  • 算法：
    • prev curr after 迭代往后操作 
public ListNode reverseList(ListNode head) {
    ListNode curr = head;
    ListNode prev = null;
    while (curr != null) {
        ListNode after = curr.next;
        curr.next = prev;
        prev = curr;
        curr = after;
    }
    return prev;
}

面试题25：合并两个排序的链表

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如输入图3.11中的链表1和链表2，则合并之后的升序链表如链表3所示。

  • 图3.11
  • 链表1：1 -> 3 -> 5
  • 链表2：1 -> 2 -> 4
  • 链表3：1 -> 1 -> 2 -> 3 -> 4 -> 5 
// 迭代
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1);
    ListNode move = dummy;
    while (true) {
        if (l1 == null) {
            move.next = l2;
            break;
        }
        if (l2 == null) {
            move.next = l1;
            break;
        }

        if (l1.val < l2.val) {
            move.next = l1;
            l1 = l1.next;
        } else {
            move.next = l2;
            l2 = l2.next;
        }
        move = move.next;
    }
    return dummy.next;
}
// 递归
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }

    if(l1.val < l2.val){
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else{
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

面试题26：树的子结构

题目：输入两棵二叉树A和B，判断B是不是A的子结构（约定空树不是任意一个树的子结构）。B是A的子结构， 即 A中有出现和B相同的结构和节点值。

public boolean isSubStructure(TreeNode A, TreeNode B) {
    if (A != null && B != null) {
        if (A.val == B.val) {
            if (treeAHasTreeB(A, B)) {
                return true;
            }
        }
        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    return false;
}
private boolean treeAHasTreeB(TreeNode A, TreeNode B) {
    if (B == null) {
        return true;
    }
    if (A == null) {
        return false;
    }
    if (A.val != B.val) {
        return false;
    }
    return treeAHasTreeB(A.left, B.left) && treeAHasTreeB(A.right, B.right);
}