LC链表题目分类详解

• 基础知识
• 链表翻转

 public static MyNode reverseList(MyNode node) {
        if (node == null) return node;
        MyNode pre = node;//上一节点
        MyNode cur = node.getNext();//当前节点
        MyNode temp;// 临时结点，用于保存当前结点的指针域（即下一结点）
        while (cur != null) {
            temp = cur.getNext();
            cur.setNext(pre);// 反转指针域的指向
            // 指针往下移动
            pre = cur;
            cur = temp;
        }
        // 最后将原链表的头节点的指针域置为null，还回新链表的头结点，即原链表的尾结点
        node.setNext(null);
        return pre;
    }

实际做的事情

实际应用
1 LeetCode] Plus One Linked List 链表加一运算

• 如何在O(n) 和 O(1)的时间复杂度下删除链表
  参考 3

leetcode 链表题目解答

• leetcode 21 合并有序链表

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode p = l1;
        ListNode q = l2;
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (p != null && q != null) {
            int val;
            if (p.val <= q.val) {
                val = p.val;
                p = p.next;  
            } else {
                val = q.val;
                q = q.next;
            }
            cur.next = new ListNode(val);
            cur = cur.next;
        }
        if (p != null) { // **注意: 这里不用while循环，直接一个if判断 + next表示就可以了。 **
            cur.next = p;
        }
        if (q != null) {
            cur.next = q;
        }
        return head.next;
    }
}

• leetcode 83 删除链表中重复元素
  • 我的解法：总体略显复杂

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            while (curNext != null && cur.val == curNext.val) {
                curNext = curNext.next;
            }
            if (curNext == null) {
                cur.next = null;
                break;
            }
            cur.next = curNext;
            cur = cur.next;
        }
        return head;
    }
}

• 大神解法

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while(cur != null && cur.next != null) {
            if(cur.val == cur.next.val) {
                cur.next = cur.next.next;  // 执行删除重复节点
            } else {
                cur = cur.next;  // 这个直到出现值不相同的节点的时候才向后移动，执行cur = cur.next;
            }
        }
        return head;
    }
}

image.png

• leetcode 141

// 自己AC,  判断链表中是否有环: 快慢指针
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode cur = head;
        ListNode p = head.next;
        while ( cur != null && p != null) {
            if (p == cur) return true;
            p = p.next;
            if (p == cur) return true;
            if (p == null) return false;
            p = p.next;
            cur = cur.next;
        }
        return false;
    }
}

• 大神简洁解法

快慢指针原理：快指针一次走两步，慢指针一次走一步，这样快指针每次比慢指针多走一步(+1), 因为是连续的，所以肯定会出现快慢指针相遇的情形，如果相遇则表示有环。

public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode quick = head;
        while (quick != null && quick.next != null) {  // 一定是quick和quick.next 作为判断条件
            quick = quick.next.next;
            slow = slow.next;
            if (quick == slow) return true;
        }
        return false;
     }

• leetcode 142: 环形链表2
  • 自己的一个解法：太慢

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head; 
        ListNode fast = head;
        ListNode cur = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == cur) return cur;
            if (slow == fast) {
                cur = cur.next;    
            }
        }
        return null;
    }
}

AC详情

• 实际的解法其实是一个数学问题： 具体详解见参考4

// 最后AC的解法
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        ListNode cur = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) { // 有环的判断条件
                break;    
            }
        }
        if (fast == null || fast.next == null) { // 无环的判断条件
            return null;
        }
        while (cur != slow) {
            cur = cur.next;
            slow = slow.next;
        }
        return cur;
    }
}

运行效果

• leetcode 92

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        
        if (head == null) return head;
        
        ListNode cur = head, pre = null; // 标记访问的节点
        
        while (m > 1) {
            --m;
            --n;
            pre = cur;
            cur = cur.next;
        }
        
        ListNode con = pre,  tail = cur;
        ListNode third; 
        while (n > 0) {
            --n;
            third = cur.next;
            cur.next = pre;
            pre = cur;
            cur = third;
        }
        if (con != null) {
            con.next = pre;    
        } else {
            head = pre;
        }
        tail.next = cur;
        return head;
    }
}

图解

参考：
1 链表翻转
2 LeetCode Plus One Linked List 链表加一运算
3 时间复杂度分别为 O（n）和 O（1）的删除单链表结点的方法
4 快慢指针寻找入口点的解法