/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode l1 = list1;
        ListNode l2 = list2;
        // 新链表头指针
        ListNode header = null;
        // 新链表后指针
        ListNode before = null;
        
        // 特别注意示例 [1,5] [1,2,4]
        while(l1 != null || l2 != null) {
            // 两者都没走到末尾，都不为空
            if (l1 != null && l2 != null) {
                // 两链表当前节点相同，加两个一样的到新链表，并同时向前走一步
                if (l1.val == l2.val) {
                    ListNode newNode1 = new ListNode(l1.val);
                    ListNode newNode2 = new ListNode(l2.val);
                    if (before != null) {
                        before.next = newNode1;
                    }
                    newNode1.next = newNode2;
                    before = newNode2;
                    // 两个相等，同时加入新链表，同时向前走一步
                    l1 = l1.next;
                    l2 = l2.next;
                    // 新链表头节点，只在为 null 的时候指定一次
                    if (header == null) {
                        header = newNode1;
                    }
                }
                // 两链表当前节点不同，加小的那个到新链表，并只将小的那个向前走一步
                else {
                    ListNode newNode = null;
                    if (l1.val < l2.val) {
                        newNode = new ListNode(l1.val);
                        // l1 当前比 l2 当前小，只把 l1 加入新链表，也只有 l1 向前走一步
                        l1 = l1.next;
                    }
                    else if (l2.val < l1.val) {
                        newNode = new ListNode(l2.val);
                        // l2 当前比 l1 当前小，只把 l2 加入新链表，也只有 l2 向前走一步
                        l2 = l2.next;
                    }
                    // 将新节点与之前的连上
                    if (before != null) {
                        before.next = newNode;
                    }
                    before = newNode;
                     // 新链表头节点，只在为 null 的时候指定一次
                    if (header == null) {
                        header = newNode;
                    }
                }
            }
            // 两链表有一者走到了末尾，将没走到末尾的那个当前节点加入新链表，并向前走一步
            else {
                ListNode newNode = null;
                if (l1 != null && l2 == null) {
                    // 只走还没走完的这个链表
                    newNode = new ListNode(l1.val);
                    l1 = l1.next;
                }
                else if (l2 != null && l1 == null) {
                    // 只走还没走完的这个链表
                    newNode = new ListNode(l2.val);
                    l2 = l2.next;
                }
                // 将新节点与之前的连上
                if (before != null) {
                    before.next = newNode;
                }
                before = newNode;
                 // 新链表头节点，只在为 null 的时候指定一次
                if (header == null) {
                    header = newNode;
                }
            }
            
        }
        return header;

    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode kStart = null;
        ListNode kCur = head;
        ListNode kEnd = null;

        ListNode preKtail = null;

        ListNode resHead = null;
        int ki = 1;
        while(kCur != null) {
            // 每次先缓存下一个节点，防止后面有变化
            ListNode nextNode = kCur.next;
            if (ki == 1) {
                // k 个一组的起始
                kStart = kCur;
            }
            if (ki == k) {
                kEnd = kCur;
                if (resHead == null) {
                    resHead = kEnd;
                }
                ki=0;
                // 切断与下一个 k 组的联系，使得反转链表的时候有尾指向null
                kEnd.next = null;
                // 上一个链表尾指向这个的最后一个（待翻转）
                if (preKtail != null) {
                    preKtail.next = kEnd;
                }
                // 反转链表
                reverseList(kStart);
                // 链表已经反转过，头成了尾巴
                preKtail = kStart;
            }
            ki++;
            kCur = nextNode;
            if (kCur == null && ki > 1) {
                // 没有任何完整的一组的情况
                if (resHead == null) {
                    resHead = kStart;
                }
                // 这些剩下的不用反转，因此上一个尾指向这一个头
                if (preKtail != null) {
                    preKtail.next = kStart;
                }
                break;
            }
        }
        return resHead;
    }

    private void reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null) {
            // 先缓存下一个节点。注意怎么反转链表，这个 Next 指针要每次循环新生成一个，不能定义一个全局的
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }
}