算法记录——链表

2.链表

2.1判断是否是回文链表

1.方法一：利用栈反转链表

/**
 * 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 boolean isPalindrome(ListNode head) {
        Stack<ListNode> listNodes = new Stack<>();
        ListNode p = head;
        //利用栈反转链表，判断是否是回文链表
        while (p != null) {//将链表中所有元素入栈
            listNodes.push(p);
            p = p.next;
        }
        while (!listNodes.empty()) {
            if (listNodes.pop().val == head.val) {//
                head = head.next;
            } else {
                return false;
            }
        }
        return true;
    }
}

2.方法2：利用快慢指针

/**
 * 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 boolean isPalindrome(ListNode head) {
    //代表快指针，一次走两步
        ListNode fast = head;
        //代表慢指针，一次走一步
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //退出循环时，如果链表节点是奇数个，快指针在尾节点，慢指针在中点。如果是偶数个，快指针还是在尾节点，慢指针在中点前一个。
        //把右半部分链表反转
        slow = reverseList(slow.next);
        while (slow != null) {
            if (head.val != slow.val) return false;//值不相同，直接返回false
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    //反转链表
    public static ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

2.2 模板题：反转链表

/**
 * 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 reverseList(ListNode head) {
        //cur：用于遍历链表元素的指针，代表当前遍历到的节点，初始化当然为head了
        ListNode cur = head;
        //pre：代表当前cur节点，反转后应该指向的节点。因为cur初始在head，反转以后就是尾节点了指向null，所以pre初始化为null
        ListNode pre = null;
        while(cur != null){//当元素还没遍历完的时候
            //在cur指向pre前，用于保存cur.next，防止链表找不到了。
            ListNode temp = cur.next;
            //让当前节点cur，指向pre
            cur.next = pre;
            //让pre变为反转链表的最前面一个节点
            pre = cur;
            //让cur移动到原链表的头节点
            cur = temp;
        }
        // 注意：pre的含义还是反转链表的头节点！
        return pre;
    }
}

复杂度分析：
时间复杂度 O(N)O(N)O(N) ： 遍历链表使用线性大小时间。
空间复杂度 O(1)O(1)O(1) ： 变量 pre 和 cur 使用常数大小额外空间。

已经是最优的解法了，还有一种递归方法就不赘述了。

2.3 分割链表(将链表分为小于某个值，等于某个值，大于某个值)

/**
 * 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 partition(ListNode head, int x) {
if (head == null || head.next == null) return head;

        //代表小于目标值区域的头和尾
        ListNode h1 = null;
        ListNode t1 = null;
        //代表大于等于目标值的头和尾
        ListNode h2 = null;
        ListNode t2 = null;
        //用于保存head的下一个节点
        //注意：这里最后拼接好了以后，小于区域的头就是整个链表的新的头节点，因此，head可以作为遍历链表的指针。
        ListNode next = head.next;
        while (head != null) {//遍历
            next = head.next;
            head.next = null;
            if (head.val < x) {//如果当前节点的val小于目标值
                if (h1 == null) {//如果当前节点是小于区域的第一个节点
                    h1 = head;
                    t1 = head;
                } else {
                    t1.next = head;
                    t1 = head;
                }
            } else {
                if (h2 == null) {//如果当前节点是大于区域的第一个节点
                    h2 = head;
                    t2 = head;
                } else {//其他情况就把该节点尾插法插入链表中
                    t2.next = head;
                    t2 = head;
                }
            }
            head = next;
        }

        //进行小于区域链表和大于等于区域链表的拼接
        if (h2 == null) {//如果没有大于等于区域
            return h1;
        }
        if (h1 == null) {//如果没有小于区域
            return h2;
        }
        //如果两种区域都有，则让小于区域的尾指针指向大于等于区域的头指针
        t1.next = h2;

        return h1;
    }
}

2.4 随机链表的赋值

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        //创建一个map，key为老链表的节点。val为新链表的节点
        HashMap<Node,Node> map = new HashMap<Node,Node>();
        Node cur = head;
        //遍历链表，设置map的key和value
        while(cur != null){
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        //再次遍历老链表，给新链表设置每一个节点的next和random
        while(cur != null){
            //cur 老链表节点
            //map.get(cur) cur对应的新链表
            map.get(cur).next = map.get(cur.next);//设置新链表的next
            map.get(cur).random = map.get(cur.random);//设置新链表的random
            cur = cur.next;
        }
        return map.get(head);
    }
}

2.5环形链表的判断

方法一：利用HashSet集合。

思路：遍历当前链表，每次遍历判断当前节点是否已经存在于set集合中。如果不存在，则把当前节点放入集合。如果已经存在，说明当前节点就是第一个入环节点。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        //创建一个set，用于存放链表中已经遍历了的节点
        HashSet<ListNode> set = new HashSet<>();
        while(head != null){
            //如果当前节点已经存在于set，说明存在环形结构
            if(set.contains(head)) return true;
            set.add(head);
            head = head.next;
        }
        return false;
    }
}

方法二：快慢指针

开始时，快慢指针都在头节点的位置。快指针一次走两步，慢指针一次走一步。

如果没有环结构，快指针一定先走到尾节点。

如果有环结构，快慢指针会在换里相遇。而相遇所要走的卷数不会大于两圈。

相遇以后，快指针/慢指针到头节点的位置。两个指针开始一次走一步。最终两个指针会在第一次入换节点相遇！(原理就不证明了)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) return null;
        //定义慢指针，一次走一步
        ListNode n1 = head.next;
        //定义快指针，一次走两步
        ListNode n2 = head.next.next;
        while(n1 != n2){//当n1 n2不相遇时循环，所以我开始时没有把两个指针都设置在头节点的位置
            if(n2.next == null || n2.next.next == null){//说明没有环结构，直接返回空
                return null;
            }
            n1 = n1.next;//慢指针一次走一步
            n2 = n2.next.next;//慢指针一次走两步
        }
        //快指针移到头节点，开始一次走一步
        n2 = head;
        while(n1 != n2){//当两个指针相遇时，就走到了第一个入环节点
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;
    }
}

2.6 链表相交

思路：两个单链表，如何判断有没有相交点呢？

1.先遍历两个链表，到尾节点时停止。如果这时候，两个链表的尾节点都不想等。说明二者不相交。

2.如果二者尾节点是同一个，则计算二者链表长度的差值。让长的链表先走差值个距离。然后，短的链表从头开始走，二者一定会在相交点相遇！

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //定义两个指针用于遍历两条链表
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int n = 0;//用于记录两条链表的差值
        while(cur1.next != null){
            cur1 = cur1.next;
            n++;
        }
        while(cur2.next != null){
            cur2 = cur2.next;
            n--;
        }
        if(cur1 != cur2){//尾节点都不想等，说明二者不相交
            return null;
        }
        //这样遍历完两条链表，n就是两条链表的长度差
        cur1 = n > 0 ? headA : headB;//让cur1指向两条链表中长的那一条
        cur2 = cur1 == headA ? headB : headA;//让cur2指向两条链表中短的那一条
        n = Math.abs(n);//n取绝对值
        while(n != 0){//让长的那条链表先移动两条链表差值的距离，再一起走，就会在相交部分汇合！
            cur1 = cur1.next;
            n--;
        }
        while(cur1 != cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
}

2.7.两数相加

思路：

/**
 * 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 addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode res = new ListNode();
            ListNode cur = res;
            int carry = 0;
            //当l1、l2中有一个不是空节点，或者还有进位，就继续循环
            while (l1 != null || l2 != null || carry != 0) {
                if (l1 != null) carry += l1.val;
                if (l2 != null) carry += l2.val;
                cur.next = new ListNode(carry % 10);//carry%10 就是该点的val
                cur = cur.next;
                carry = carry / 10;// carry/10 就是下一个点的进位
                if (l1 != null) l1 = l1.next;//l1 没有遍历完
                if (l2 != null) l2 = l2.next;
            }
            return res.next;
        }
}

2.8.合并两个有序链表

/**
 * 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 res = new ListNode();
            ListNode cur = res;

            while (list1 != null && list2 != null) {
                if (list1.val <= list2.val) {//如果l1链表的值更小
                    cur = cur.next = list1;
                    list1 = list1.next;
                } else {
                    cur = cur.next = list2;
                    list2 = list2.next;
                }
            }
            while (list1 != null) {//如果1还没遍历完
                cur = cur.next = list1;
                list1 = list1.next;
            }
            while (list2 != null) {//如果2还没遍历完
                cur = cur.next = list2;
                list2 = list2.next;
            }
            return res.next;
        }
}

2.9 反转链表2

题解参考：leetcode

/**
 * 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 reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0, head);
        ListNode g = dummy;
        ListNode p = dummy;
        //g指向的下一个节点就是要开始反转的节点
        for (int i = 0; i < left - 1; i++) {
            g = g.next;
            p = p.next;
        }
        //p指向第left个节点
        p = p.next;
        for (int i = 0; i < right - left; i++) {
            ListNode temp = p.next;
            p.next = p.next.next;
            temp.next = g.next;
            g.next = temp;
        }

        return dummy.next;
    }
}

2.10.K个一组反转链表

        本题思路和上一题差不多。举一反三，还是主要用g、p两个指针反转链表。

        每组链表反转之前，g的next指向的都是待反转链表的第一个节点，p指向的就是待反转链表的第一个节点。
        要注意的就是每次反转完链表p指针指向的就是反转后链表的最后一个元素，同时它的next也是下一组待反转链表的第一个元素，所以每次每组反转完以后，都要把p赋值给g。

/**
 * 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 dummy = new ListNode(0, head);
        ListNode g = head;
        //计算一共有多少个节点，用来算要反转几组链表
        int count = 0;
        while (g != null) {
            g = g.next;
            count++;
        }
        g = dummy;
        ListNode p = g.next;
        //遍历
        for (int i = 0; i < count / k; i++) {
            p = g.next;
            //反转的每组链表
            for (int j = 1; j < k; j++) {
                ListNode temp = p.next;
                p.next = p.next.next;
                temp.next = g.next;
                g.next = temp;
            }
            //每组链表反转完，让cur的next指向下一组待反转链表第一个
            g = p;
        }

        return dummy.next;
    }
}