LeetCode链表部分习题

138. 复制带随机指针的链表

问题：请实现 copyRandomList 函数，复制一个复杂链表。
在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，
还有一个 random 指针指向链表中的任意节点或者 null。

public class CopyRandomList {
    /**
     * 节点定义
     */
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        if (head==null){
            return head;
        }
        HashMap<Node,Node> map=new HashMap<>();
        Node cur=head;
        // 初始化哈希表
        while (cur!=null){
            map.put(cur,new Node(cur.val));
            cur=cur.next;
        }
        cur=head;
        // 复制next和random引用
        while (cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);
    }
}

141. 环形链表

判断链表是否有环

public boolean hasCycle2(ListNode head) {
    if (head==null||head.next==null){
        return false;
    }
    ListNode slow=head;
    ListNode fast=head.next;
    while (slow!=fast){
        if(fast==null||fast.next==null){
            return false;
        }
        slow=slow.next;
        fast=fast.next.next;
    }
    //当快指针终将追上慢指针时，一定有环
    return true;
}

148. 排序链表

public class SortList {
    /**
     * 链表定义
     */
    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;
        }
    }

    /**
     * 递归：归并排序
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head){
        // 结束条件
        if (head == null || head.next == null) {
            return head;
        }
        // 使用快慢指针，当fast指向终点时，slow指向中点
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        //将链表断开
        slow.next = null;
        //左右链表分别递归分割
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }
}

160. 相交链表

找到两个单链表相交的起始节点。

public class GetIntersectionNode {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            this.val = x;
            next = null;
        }
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA;
        ListNode pB = headB;
        while (pA != pB) {
            pA =pA!=null? pA.next:pB;
            pB =pB!=null? pB.next:pA;
        }
        return pA;
    }
}

206. 反转链表

public class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        this.val=x;
    }
}

/**
 * 将当前节点的 next 指针改为指向前一个元素。
 * 由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。
 * 在更改引用之前，还需要另一个指针来存储下一个节点。
 * @param head
 * @return
 */
public ListNode reverseList(ListNode head){
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

234. 回文链表

请判断一个链表是否为回文链表。

public class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        this.val=x;
    }
}
public boolean isPalindrome(ListNode head) {
    List<Integer> vals = new ArrayList<>();

    // 1.复制链表值到数组
    ListNode currentNode = head;
    while (currentNode != null) {
        vals.add(currentNode.val);
        currentNode = currentNode.next;
    }

    // 2.使用双指针
    int front = 0;
    int back = vals.size() - 1;
    while (front < back) {
        // Note that we must use ! .equals instead of !=
        // because we are comparing Integer, not int.
        if (!vals.get(front).equals(vals.get(back))) {
            return false;
        }
        front++;
        back--;
    }
    return true;
}

237. 删除链表中的节点

private void deleteNode(ListNode node) {
    //让当前结点值为下一个结点值
    node.val=node.next.val;
    //修改指针
    node.next=node.next.next;
}

328. 奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。
请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

public ListNode oddEvenList(ListNode head) {
    if (head == null) {
        return head;
    }
    // head为奇数头节点，evenHead为偶数头节点
    ListNode evenHead = head.next;
    ListNode odd = head, even = evenHead;
    while (even != null && even.next != null) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;

}