LeetCode初级算法——链表篇

LeetCode初级算法——链表篇

什么是链表

链表分为单链表和双链表

1. 单链表

链表中的每个元素实际上是一个单独的对象，而所有的对象都通过每个元素中的引用字段连接在一起。

2. 双链表

与单链表不同的是，双链表的每个结点都含有 `两个引用字段`

Exc1 - 删除链表的倒数第N个节点

Core

1. 求出要被删除的节点前一个节点，让它的Next = next.next，前提先求出链表的长度

CoreCode

    int length = getLength(head) - n;
    if (length == 0)
        return head.next;
    for (int i = 0; i < length-1; i ++) {
        pre = pre.next;
    }
    pre.next = pre.next.next;

Exc2 - 反转链表

Core

1. 可以利用栈的特点，<strong style="color: red">“先进后出”</strong>，入栈之后，再pop出栈
2. 双链表解决

CoreCode

(// 1. Stack
	public ListNode stackReverse(ListNode head) {
       	// 拿出栈顶元素
        ListNode node = stack.pop();
        ListNode res = node;
        while(stack.isEmpty()){
            ListNode temp = stack.pop();
            node.next = temp;
            node = node.next;
        }
        // 因为会生成环，所以末尾next为null, 不然环就会死循环
        node.next = null;
        
    }
// 2. double linked list
	public ListNode doubleLinkedList(ListNode head) {
        ListNode newList = null;
        while(head != null) {
            ListNode pre = head.next;
            head.next = newList;
            newList = head;
            head = pre;
        }
    }

Exc3 - 合并两个有序链表

Core

1. 使用递归的思想，对两个链表进行比较，不断进行递归调用比较大小传参，再放入新的链表中
2. 遍历两个链表，比较每个链表的头节点，比到有一个链表为空，另一个链表直接挂入新的链表中

CoreCode

// 递归
	public ListNode mergeTwoLists(ListNode list1, ListNode list2 ){
        ListNode resList = (list1.val > list2.val)? list1 : list2;
        resList.next = mergeTwoLists (resList.next, resList == list1? list2: list1)
        return resList;
    }
// 遍历
	public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode res = new ListNode(0);
        ListNode curr = res;
        while(list1 != null && list2 != null ) {
            if (list1.val >= list2.val ) {
                curr = list2;
                list2 = list2.next;
            } else {
                curr = lis1;
                list1 = list1.next;
            }
            curr = curr.next;
        }
        curr.next = list1 == null ? list2 : list1;
        return res.next;
    }

Exc4 - 回文链表

Core

1. 利用快慢指针截取后半段，再进行遍历比较
2. 利用栈的特点,计算出长度，实际上只需要比对前半段

CoreCode

// 快慢指针反转后半部分
	public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast,next.next;
        }
        // 如果是偶数，则slow就在后半段的头节点
        // 如果为奇数，则要进一位
        if(fast != null) {
            slow = slow.next;   
        }
        slow = reverse(slow);
        fast = head;
    	while(slow != null) {
            if (slow.val != fast.val)
                return false;
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }
// 利用栈的特点
	public boolean isPalindromeByStack(ListNode head) {
        ListNode temp = head;
        Stack<Integer> stack = new Stack();
        int len = 0;
        while(temp != null ){
            stack.push(temp.val);
            temp = temp.next;
            len ++;
        }
        // len长度/2
        len >>= 1;
        while(len-- >=0) {
            if (head.val != stack.pop())
                return false;
            head = head.next;
        }
        return true;
    }

Exc5 - 环形链表

Core

1. m快n慢，遍历比较节点是否相同 (m > n )  CoreCode m = 3, n =1;
2. 利用set集合

CoreCode

// 3快1慢
	public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next.next;
            if (fast == slow)
                return true;
        }
        return false;
    }
// set集合
`	public boolean hasCycleBySet(ListNode head) {
    	Set<ListNode> set = new HashSet<>();
    	while(head != null) {
            if (set.contains(head))
                return true;
            set.add(head);
            head = head.next;
        }
    	return false;
	}