链表题总结

hot100

相交链表

题目链接：
160.相交链表
代码：

/**
 * 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 p1 = headA, p2 = headB;

        while (p1 != p2)
        {
            p1 = p1 != null ? p1.next:headB;
            p2 = p2 != null ? p2.next:headA;
        }
        return p1;
        
    }
}

反转链表

题目链接：
206.反转链表
代码：

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode tmp;
        ListNode pre = null;
        ListNode curr = head;

        while(curr != null){
            tmp = curr.next;
            curr.next = pre;

            pre = curr;
            curr = tmp;
        }
        return pre;

    }
}

回文链表

题目链接：
234.回文链表
代码：

class Solution {
    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;

            pre = curr;
            curr = next;
        }
        return pre;
    }
    public ListNode cut(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        ListNode mid = cut(head);
        ListNode mids = reverse(mid.next);
        boolean result = true;
        ListNode l1 = head, l2 = mids;
        while (result && l2 != null) {
            if (l1.val != l2.val) {
                result = false;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        return result;
    }
}

环形链表

题目链接：
141.环形链表
代码：

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                return true;
            }
        }

        return false;
        
    }
}

环形链表2

题目链接：
142.环形链表2
代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;

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

合并两个有序链表

题目链接：
21.合并两个有序链表
代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (list1 == null && list2 == null) return null;
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        ListNode l;
        if (list2.val <= list1.val)
        {
            l = list2;
            list2 = list2.next;
        }else
        {
            l = list1;
            list1 = list1.next;
        }
        ListNode tmp = l;

        while(list1 != null && list2 != null)
        {
            if (list2.val <= list1.val)
            {
                tmp.next = list2;
                list2 = list2.next;
            }else
            {
                tmp.next = list1;
                list1 = list1.next;
            }
            tmp = tmp.next;
        }

        tmp.next = (list1 == null) ? list2:list1;
        return l;
        
    }
}

两数相加

题目链接：
2.两数相加
代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int cary = 0;
        while (l1!= null || l2 != null) {
            int x = (l1 == null) ? 0 : l1.val;
            int y = (l2 == null) ? 0 : l2.val;
            int sum = x + y + cary;
            ListNode node = new ListNode(sum % 10);
            cary = sum / 10;
            curr.next = node;
            curr = curr.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (cary != 0) {
            ListNode node = new ListNode(cary);
            curr.next = node;
        }
        return dummy.next;
    }
}

删除链表的倒数第N个结点

题目链接：
19.删除链表的倒数第N个结点
代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode dummy = new ListNode(-1,head);
        ListNode first = dummy;
        ListNode second = dummy;
        for (int i = 0; i <= n; i ++){
            first = first.next;
        }
        while (first != null){
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}

两两交换链表中的节点

题目链接：
24.两两交换链表中的节点
代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode dummy = new ListNode(-1,head);
        ListNode curr = dummy;
        ListNode tmp;
        ListNode first;
        ListNode second;

        while (curr.next != null && curr.next.next != null){
            tmp = curr.next.next.next;
            first = curr.next;
            second = curr.next.next;
            curr.next = second;
            second.next = first;
            first.next = tmp;
            curr = first;
        }
        return dummy.next;
    }
}

K 个一组翻转链表

题目链接：
25.K 个一组翻转链表
代码：

public class Solution {
    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;

        }
        return pre;
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0,head);
        ListNode pre = dummy, end = dummy;
        while (end != null) {
            for (int i = 0; i < k && end!= null; i ++) {
                end = end.next;
            }
            if (end == null) break;
            ListNode start = pre.next;
            ListNode next = end.next;
            end.next = null;
            pre.next = reverse(start);
            start.next = next;

            pre = start;
            end = pre;
        }
        return dummy.next;

    }
}

随机链表的复制

题目链接：
138.随机链表的复制
代码：

/*
// 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 {
    Map<Node,Node> map = new HashMap<>();
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        if (! map.containsKey(head))
        {
            Node node = new Node(head.val);
            map.put(head,node);
            node.next = copyRandomList(head.next);
            node.random = copyRandomList(head.random);
        }
        return map.get(head);
    }
}

排序链表

题目链接：
148.排序链表
代码：

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next!=null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(fast);

        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

        while (left != null && right != null) {
            if (left.val <= right.val) {
                curr.next = left;
                left = left.next;
            }else{
                curr.next = right;
                right = right.next;
            }
            curr = curr.next;
        }
        curr.next = left != null ? left:right;

        return dummy.next;

    }
}

合并 K 个升序链表

题目链接：
23.合并 K 个升序链表
代码：

class Solution {
    public ListNode merge (ListNode head1, ListNode head2){
        ListNode dummy = new ListNode(0);
        ListNode tmp = dummy, tmp1 = head1, tmp2 = head2;

        while (tmp1 != null && tmp2 != null){
            if (tmp1.val <= tmp2.val){
                tmp.next = tmp1;
                tmp1 = tmp1.next;
            }else{
                tmp.next = tmp2;
                tmp2 = tmp2.next;
            }
            tmp = tmp.next;
        }
        if (tmp1 != null) tmp.next = tmp1;
        if (tmp2 != null) tmp.next = tmp2;
        return dummy.next;
    }
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = null;
        for (int i = 0; i < lists.length; i ++){
            res = merge(res,lists[i]);
        }
        return res;

    }
}

LRU缓存

题目链接：
146.LRU缓存
代码：

class LRUCache {
    class DLink{
        int key;
        int value;
        DLink pre, next;
        DLink() {}
        DLink(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    DLink head, tail;
    int size;
    int capacity;
    Map<Integer, DLink> map = new HashMap<>();

    public LRUCache(int capacity) {
        head = new DLink();
        tail = new DLink();
        head.next = tail;
        tail.pre = head;
        this.size = 0;
        this.capacity = capacity;

    }
    
    public int get(int key) {
        DLink node = map.get(key);
        if (node == null) {
            return -1;
        }
        moveTohead(node);
        return node.value;
        
    }
    
    public void put(int key, int value) {
        DLink node = map.get(key);
        if (node == null) {
            DLink n = new DLink(key,value);
            map.put(key, n);
            addToHead(n);
            size ++;
            if (size > capacity) {
                DLink deleNode = removeTail();
                map.remove(deleNode.key);
                size --;
            }
        }else {
            node.value = value;
            moveTohead(node);
        }

    }

    public void addToHead(DLink node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        // DLink next = head.next;
        // head.next = node;
        // node.pre = head;
        // node.next = next;
        // next.pre = node;
    }
    public void removeNode(DLink node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    public DLink removeTail() {
        DLink node = tail.pre;
        removeNode(node);
        return node;
    }
    public void moveTohead(DLink node) {
        removeNode(node);
        addToHead(node);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */