链表

1 反转链表

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
	if (head == null || head.next == null) retrun head;
        // 反转后链表
	ListNode res = null;
        // 头结点的下一个节点
	ListNode next = null;
	while (head != null) {
            // 将头节点的下一个节点取出
	    next = head.next;
            // 头结点后将反转的链表进行拼接
	    head.next = res;
            // 反转地址更新
	    res = head;
            // 头节点地址更新
	    head = next;
	}
	return res;
    }
}

2 链表中k个节点一组进行翻转，最后不足k个的直接拼接

public class Solution {
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if (head == null || head.next == null || k < 2) return head;
        ListNode res = new ListNode(-1); // 返回数据
        res.next = head;
        int length = 0; // 链表长度
        while (head != null) {
            length++;
            head = head.next;
        }
        ListNode pre = res; // 当前节点的上一个节点
        ListNode cur = res.next; // 当前节点
        ListNode next = null;
        for (int i = 0; i < length / k; i++) {
	    // pre作为每一小段链表的头节点，负责衔接
            for (int j = 1; j < k; j++) {
                next = cur.next;
                cur.next = next.next;
                next.next = pre.next;
                pre.next = next;
            }
            pre = cur;
            cur = cur.next;
        }
        return res.next;
    }
}

3 链表内指定区间反转

public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        if (head == null || head.next == null) return head;
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode pre = res;
        for (int i = 1; i < m; i++) {
            pre = head;
            head = head.next;
        }
        ListNode temp = null;
        for (int i = 0; i < n - m; i++) {
            temp = head.next;
            head.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return res.next;
    }
}

4 判断一个链表是否是回文链表

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        // 快慢指针确定中间值，遍历过程中，前半段进行链表翻转
        // 中间值确定后 从头和中间值开始进行遍历比较
        if (head == null) return false;
        if (head.next == null) return true;
        ListNode left = head;
        ListNode right = head;
        ListNode res = null;
        ListNode temp = null;
        while (right != null && right.next != null) {
            // 快慢指针
            left = left.next;
            right = right.next;
            if (right.next == null) break;
            right = right.next;
            
            // 翻转链表
            temp = head.next;
            head.next = res;
            res = head;
            head = temp;
        }
        left = left.next;
        while (left != null) {
            if (res.val != left.val) return false;
            res = res.next;
            left = left.next;
        }
        return true;
    }
}

5 两个链表生成相加链表

public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        // 利用栈的先进后出特性
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        //往栈里面添加元素
        ListNode node1 = head1;
        ListNode node2 = head2;
        while (node1 != null) {
            stack1.push(node1.val);
            node1 = node1.next;
        }
        while (node2 != null) {
            stack2.push(node2.val);
            node2 = node2.next;
        }
        //开始相加
        int carry = 0;
        ListNode head = new ListNode(0);
        ListNode tailer = head;
        while(!stack1.empty() || !stack2.empty() || carry != 0) {
            int a = 0;
            int b = 0;
            if (!stack1.empty()) {
                a = stack1.pop();
            }
            if (! stack2.empty()) {
                b = stack2.pop();
            }
            int sum = a + b + carry;
            int num = sum % 10;
            carry  = sum / 10;
            ListNode nodeNum = new ListNode(num);
            // 尾插法
            tailer.next = nodeNum;
            tailer = tailer.next;
        }
        head = head.next;
        // 反转后链表
        ListNode res = null;
        // 头结点的下一个节点
        ListNode next = null;
        while (head != null) {
            // 将头节点的下一个节点取出
            next = head.next;
            head.next = res;
            res = head;
            head = next;
        }
        return res;
    }
}

6 判断链表中是否有环

public class Solution {
    public boolean hasCycle(ListNode head) {
        // 快慢指针相遇说明有环
        if (head == null || head.next == null) return false;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }
}

7 链表中环的入口节点

思路：
1）同上一题，使用快慢指针方法，判定是否存在环，并记录两指针相遇位置(Z)；

2）将两指针分别放在链表头(X)和相遇位置(Z)，并改为相同速度推进，则两指针在环开始位置相遇(Y)。

证明如下：

如下图所示，X,Y,Z分别为链表起始位置，环开始位置和两指针相遇位置，则根据快指针速度为慢指针速度的两倍，可以得出：

2*(a + b) = a + b + n * (b + c)；
即
a = (n - 1) * b + n * c;

a = (n - 1)(b + c) + c;

注意到b+c恰好为环的长度，故可以推出，如将此时两指针分别放在起始位置和相遇位置，并以相同速度前进，当一个指针走完距离a时，另一个指针恰好走出 绕环n-1圈加上c的距离。
故两指针会在环开始位置相遇。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        ListNode meetNode = null;
        // 先确定有环
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) { // 快慢指针相遇，说明有环
                meetNode = fast;
                break;
            }
        }
        if (meetNode == null) return null; // 为空 没有相遇 返回null
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

8 查找两个链表是否有公共节点

public class Solution {
    // pHead1: 0-1-2-3-4-5-null
    // pHead2: a-b-4-5-null
    // 两个指针同时移动，移动到头 遍历对方的链接 时间复杂度O(n + m)
    // p1：0-1-2-3-4   -5-null-a-b-4-5-null
    // p2: a-b-4-5-null 0-1   -2-3-4-5-null
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) return null;
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
            if (p1 != p2) {
                if (p1 == null) p1 = pHead2;
                if (p2 == null) p2 = pHead1;
            }
        }
        return p1;
    }
}

9 合并有序链表

public class Solution {
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // write code here
        ListNode head = new ListNode(0);
        ListNode next = head;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                next.next = l1;
                l1 = l1.next;
            } else {
                next.next = l2;
                l2 = l2.next;
            }
            next = next.next;
        }
        if (l1 != null) {
            next.next = l1;
        }
        if (l2 != null) {
            next.next = l2;
        }
        return head.next;
    }
}

10 合并K个有序链表 O(logK)

public class Solution {
    // 知识点 1 分治，2 两个有序链表合并，2a 尾插法
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0) return null;
        return mergeKLists(lists, 0, lists.size() - 1);
    }
    private ListNode mergeKLists(ArrayList<ListNode> lists, int left, int right) {
        if (left >= right) {
            return lists.get(left);
        }
        int mid = left + (right - left) / 2;
        ListNode l1 = mergeKLists(lists, left, mid);
        ListNode l2 = mergeKLists(lists, mid + 1, right);
        return mergeTwoList(l1, l2);
    }
    
    private ListNode mergeTwoList(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode next = head;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                next.next = l1;
                l1 = l1.next;
            } else {
                next.next = l2;
                l2 = l2.next;
            }
            next = next.next;
        }
        if (l1 != null) {
            next.next = l1;
        }
        if (l2 != null) {
            next.next = l2;
        }
        return head.next;
    }
}

11 单链表排序

public class Solution {
    // 知识点 1 快慢指针找中点，2 分治，3 合并有序链表，3a尾插法
    public ListNode sortInList (ListNode head) {
        // write code here
        if (head == null || head.next == null) return head;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode next = slow.next;
        slow.next = null;
        ListNode left = sortInList(head);
        ListNode right = sortInList(next);
        return mergeTwoList(left, right);
    }
    
    private ListNode mergeTwoList(ListNode left, ListNode right) {
        ListNode head = new ListNode(0);
        ListNode next = head;
        while (left != null && right != null) {
            if (left.val < right.val) {
                next.next = left;
                left = left.next;
            } else {
                next.next = right;
                right = right.next;
            }
            next = next.next;
        }
        next.next = left != null ? left : right;
        return head.next;
    }
}

12 链表中倒数第k个节点

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if (head == null || head.next == null) return head;
        ListNode left = head;
        ListNode right = head;
        for (int i = 0; i < k; i++) {
            if (right == null) return null;
            right = right.next;
        }
        while (right != null) {
            right = right.next;
            left = left.next;
        }
        return left;
    }
}

13 删除链表倒数第n个节点

public class Solution {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        ListNode first = head;
        ListNode second = head;
        for (int i = 1; i < n; i++) {
            first = first.next;
        }
        ListNode pre = null;
        //first到尾节点， second到待删除节点
        while(first.next != null) {
            pre = second;
            second =  second.next;
            first = first.next;
        }
        //删除second节点
        if(pre != null) {
            pre.next = second.next;
        } else {
            //考虑删除头节点的情况
            head = head.next;
        }
        return head;
    }
}

14 ## 删除有序链表中重复的元素

public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if (head == null || head.next == null) return head;
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode pre = res;
        ListNode right = head.next;
        ListNode temp = null;
        while (right!=null) {
            if (pre.next.val == right.val) {
                temp = pre;
                right = right.next;
            } else {
                if (temp != null) {
                    pre.next = right;
                    temp = null;
                } else {
                    pre = pre.next;
                }
                right = right.next;
            }
        }
        if (temp != null) {
            pre.next = right;
            temp = null;
        }
        return res.next;
    }
}