第二章：链表问题

打印两个有序链表的公共部分

/**
 * 给定两个有序链表的头指针head1和head2,打印两个链表的公共部分
 * @param head1
 * @param head2
 */
public static void printCommonPart(Node head1,Node head2) {
    // 有序 则说明，我们可以用双指针思想，找到相同的点
    while (head1 != null && head2 != null) {
        if (head1.value > head2.value) {
            head1 = head1.next;
        } else if (head1.value < head2.value) {
            head2 = head2.next;
        } else {
            // 如果相等，说明到达了公共节点
            System.out.println(head1.value);
            head1 = head1.next;
            head2 = head2.next;
        }
    }
}

在单链表和双链表中删除倒数第K个节点

单链表

/**
 * 单链表删除倒数第k个节点
 * 假如链表长度为N，则删除倒数第K个点，就需要找到倒数K点的前一个点，也就是N-K位置
 * 我们每遍历一个点，k-1
 * 这里需要想一下，比如：
 * 1->2->3 k=4 : 3 2 1 ,发现最终k>0 说明倒数第K个点，已经超出范围了
 * 1->2->3 k=3 : 2 1 0 ,发现k=0, 说明删除的就是头结点，返回头结点下一个
 * 1->2->3 k=2 : 1 0 -1,k<0, 说明删除的点在中间 这时候我们从头遍历，K+1，则第一遍遍历为K-N,则第二遍当K=0时，则就是遍历到N-K的位置
 * @param head
 * @param lastKth
 */
public static Node removeLastKthNode(Node head,int lastKth) {
    if (head == null || head.next == null || lastKth < 0) {
        throw new RuntimeException("输入参数有误");
    }
    // 这里用一个指针遍历，因为第二遍我们还需要找到头结点
    Node cur = head;
    while (cur != null) {
        lastKth--;
        cur = cur.next;
    }
    if (lastKth > 0) {
        throw new RuntimeException("删除结点超出范围");
    } else if (lastKth == 0) {
        return head.next;
    }
    // 这里就剩下 K < 0 情况
    cur = head;
    while (lastKth != 0) {
        lastKth++;
        cur = cur.next;
    }
    cur.next = cur.next == null ? null : cur.next.next;
    return head;
}

双链表

/**
 * 双链表结构与单链表就是多了个前指针，我们在删除时需要注意
 *
 * @param head
 * @param lastKth
 * @return
 */
public static Node removeLastKthNode(Node head, int lastKth) {
    if (head == null || head.next == null || lastKth < 1) {
        throw new RuntimeException("参数异常");
    }
    Node cur = head;
    while (cur != null) {
        lastKth--;
        cur = cur.next;
    }
    if (lastKth == 0) {
        head = head.next;
        head.before = null;
    }
    if (lastKth < 0) {
        cur = head;
        while (lastKth != 0) {
            cur = cur.next;
            lastKth++;
        }
        // 当前就找到了要删除的点
        cur.next = cur.next.next;
        Node tmp = cur.next;
        if (tmp != null) {
            tmp.before = cur;
        }
    }
    return head;
}

删除链表的中间节点

/**
 * 删除中间节点：
 * 1->2 删除 1
 * 1->2->3 删除 2
 * 问题的关键就是要找到中间这个点，通过前一个点进行删除
 * @param head
 * @return
 */
public static Node removeMidNode(Node head) {
    if (head == null || head.next == null) {
        return head;
    }
    // 利用快慢指针，快指针一次走两步，慢指针一次走一步
  	// 这里快指针先走一步，则最终slow的下一个点就是中间点
    Node fast = head.next.next;
    Node slow = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    slow.next = slow.next.next;
    return head;
}

反转单向和双向链表

/**
 * 反转单向链表
 *
 * @param head
 * @return
 */
public static Node reverseList(Node head) {
    Node pre = null;
    Node next = null;
    while (head != null) {
        next = head;
        head = head.next;
        next.next = pre;
        pre = next;
    }
    return next;
}

/**
 * 反转双向链表
 *
 * @param head
 * @return
 */
public static Node reverseList(Node head) {
    Node pre = null;
    Node next = null;
    while (head != null) {
        next = head.next;
        head.next = pre;
        head.before = next;
        pre = head;
        head = next;
    }
    return pre;
}

反转部分单向链表

/**
 * 反转部分链表
 */
public static Node reverseFromToNode(Node head, int from, int to) {
    // 统计链表长度
    int len = 0;
    Node node1 = head;
    // 记录from 和 to的前后节点
    Node fPre = null;
    Node tPos = null;
    while (node1 != null) {
        len++;
        // 确定from前一个节点
        fPre = len == from - 1 ? node1 : fPre;
        // 确定to后一个节点
        tPos = len == to + 1 ? node1 : tPos;
        node1 = node1.next;
    }
    if (from > to || from < 1 || to > len) {
        return head;
    }
    // 判断from是不是在头结点，确定需要反转的头结点
    node1 = fPre == null ? head : fPre.next;
    Node node2 = node1.next;
    node1.next = tPos;
    Node next = null;
    // 反转
    while (node2 != tPos) {
        next = node2.next;
        node2.next = node1;
        node1 = node2;
        node2 = next;
    }
    if (fPre != null) {
        // node1 现在就反转前的to节点
        fPre.next = node1;
        return head;
    }
    return node1;
}