【檀越剑指大厂--算法】链表总结

1.重排链表(剑指offer-026-java)

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

public void reorderList(ListNode head) {
    //hash法
    if (head == null) {
        return;
    }
    List<ListNode> list = new ArrayList<>();
    while (head != null) {
        list.add(head);
        head = head.next;
    }
    int i = 0, j = list.size() - 1;
    while (i < j) {
        list.get(i).next = list.get(j);
        i++;
        if (i == j) {
            break;
        }
        list.get(j).next = list.get(i);
        j--;
    }
    list.get(i).next = null;
}

2.回文链表(234)

考察:栈的使用

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true
示例 2：

输入：head = [1,2]
输出：false

public class LC08_234_isPalindrome {

    //用栈解决
    public static boolean isPalindrome(ListNode head) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        ListNode h1 = head;
        while (h1 != null) {
            linkedList.addFirst(h1.val);
            h1 = h1.next;
        }
        ListNode h2 = head;
        while (h2 != null) {
            Integer pop = linkedList.pop();
            if (!pop.equals(h2.val)) {
                return false;
            }
            h2 = h2.next;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode link = ListNode.createLink回文();
        ListNode.printLink(link);
        System.out.println();
        System.out.println(isPalindrome(link));
    }
}

3.反转链表(206)

考察:迭代–递归–栈

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

public class LC010_206_ReverseList {
    //方法一:用栈实现
    public static ListNode reverseListIterative(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        //这里很关键,不能定义为null--初始化一个临时节点
        ListNode res = new ListNode();
        ListNode temp = res;
        while (!stack.isEmpty()) {
            temp.next = stack.pop();
            temp = temp.next;

        }
        temp.next = null;
        return res.next;
    }

    //方法二:递归实现
    public static ListNode reverseListIterative1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode listNode = reverseListIterative1(head.next);
        head.next.next = head;
        head.next = null;
        return listNode;
    }


    //方法三:迭代实现--节点左移
    public static ListNode reverseListIterative2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            //临时保存下一个节点节点
            ListNode temp = curr.next;
            //前节点给后节点
            curr.next = pre;
            //当前节点给前节点
            pre = curr;
            //原始后节点给当前节点
            curr = temp;
        }
        return pre;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.createLink();
        System.out.println("遍历输出创建好的链表:");
        ListNode.printLink(head);
        System.out.println();
        System.out.println("采用迭代方法反转后的单链表:");
        System.out.println();
        System.out.println("采用递归方法反转后的单链表");
        System.out.println();
        System.out.println("迭代实现");
        ListNode result3 = LC010_206_ReverseList.reverseListIterative2(head);
        ListNode.printLink(result3);
        System.out.println();
        System.out.println("递归实现");
    }
}

4.相交链表(160)

考察:链表相交问题

走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

public class LC012_160_getIntersectionNode {
    //先走a,再把a的指针给b  交换指针指向
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode a = headA, b = headB;
        while (a != b) {
            a = a != null ? a.next : headB;
            b = b != null ? b.next : headA;
        }
        return a;
    }

    public static void main(String[] args) {
        ListNode link1 = ListNode.createLink();
        ListNode link2 = ListNode.createLink();
        ListNode intersectionNode111 = getIntersectionNode(link1, link2);
        ListNode.printLink(intersectionNode111);
    }
}

5.环形链表(141)

考察:

• 快慢指针
• hash 表法

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

public class LC014_141_hasCycle {
    //快慢指针
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null){
            return false;
        }
        ListNode fast = head, slow = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    //hash表法
    public static boolean hasCycle2(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (!set.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }

    public static void main(String[] args) {
        ListNode link = ListNode.createLink环();
        System.out.println(hasCycle(link));
    }
}

6.移除链表元素(203)

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：