LeetCode 链表题目基本操作总结

链表题目基本操作总结。
在做题时可以考虑使用dummy node,双指针,快慢指针等技巧帮助解题。
特殊情况如需要考虑链表是否为空,或者是否只有1个节点,一般都可以直接返回。

删除节点

给出了头结点,并且给出了待删除节点的特征(值为n,第n个),要求返回删除后的链表。
删除节点的基本操作是记录目标节点的前节点pre,将pre.next设置为cur.next。需要考虑目标节点是头结点的情况。所以一般都会使用dummy node,并将dummy.next指向头结点head,最后返回dummy.next。

1.给出头结点,删除值为n的节点。

203. 移除链表元素 简单
这种题目就是标准类型,模板代码:

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        while (head != null) {
            if (head.val == val) {
                pre.next = head.next;
            } else {
                pre = pre.next;
            }
            head = head.next;
        }
        return dummy.next;
    }
}
2.替换值模拟删除节点

237. 删除链表中的节点 简单
这种题目直接给出需要删除的节点,注意不要陷入思维定式,虽然叫删除,但实际是将下一个节点的值复制到目标节点。

class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}
3.删除链表中的重复元素

83. 删除排序链表中的重复元素 简单
82. 删除排序链表中的重复元素 II 中等
删除重复元素的题目需要注意:
1.重复元素是否保留1个。
2.链表是否有序.
这两道题的链表都是有序的,就只用判断相邻元素,唯一的区别是是否保留1个重复的元素。
83题这种题型head.next才是需要删除的目标节点,所以就不用记录pre节点。当然也可以创建两个指针分别指向cur和pre,不过代码稍微要多一些。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        while (head != null && head.next != null) {
            if (head.val == head.next.val) {
                head.next = head.next.next;
            } else {
                head = head.next;
            }
        }
        return dummy.next;
    }
}

82题和83题不同在于82题可能会删除头结点,所以我们可以考虑比较cur.next和cur.next.next,另外需要考虑到第一次出现的重复元素也需要被删除,所以需要做一个标记:

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        boolean flag = false;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                flag = true;
                cur.next = cur.next.next;
            } else if (flag) {
                flag = false;
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        if (flag) cur.next = cur.next.next;
        return dummy.next;
    }
}

链表反转

将每一个节点的next指向自己的前节点。有迭代和递归两种方式实现。
206. 反转链表 简单
这是一道标准题,迭代实现,需要考虑3个指针,pre/cur/next:

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

递归实现,利用了递归的特性,代码量更少。
直接返回了队尾的节点作为反转后的头节点,同时每次将下一个节点的next指向自己。
要注意的是需要把自己的next设为null,防止原链表的头结点出现环,总体来说非常巧妙:

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}

92. 反转链表 II 中等
稍微进阶一点,反转链表的一部分,找到起始节点开始翻转,翻转一定的数量后结束,会修改原链表的结构。

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null || m == n) return head;
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode pre = dummy;
        // 找到翻转的起始节点的前节点
        for (int i = 1; i < m; i++) {
            pre = pre.next;
        }
        // 找到翻转结束的后节点
        ListNode after = pre.next;
        for (int i = 0; i < n - m + 1; i++) {
            after = after.next;
        }
        // 开始翻转
        ListNode re = reverse(pre.next, n - m);
        pre.next = re;
        // 在结尾接上after
        while (re.next != null) {
            re = re.next;
        }
        re.next = after;
        return dummy.next;
    }

    private ListNode reverse(ListNode head, int deep) {
        if (head.next == null || deep == 0) return head;
        ListNode p = reverse(head.next, --deep);
        head.next.next = head;
        head.next = null;
        return p;
    }
}

寻找倒数第n个节点

这种都是使用双指针找到对应节点。
19. 删除链表的倒数第N个节点 中等
找到链表的倒数第n个节点,定义两个指针指向头结点,将其中一个指针向前移动n个位子,然后两个指针一起移动,直到快指针为null时,慢指针即为倒数n个节点。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        for (int i = 0; i < n + 1; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // slow.next即为需要删除的节点
        slow.next = slow.next.next;
        return dummy.next;
    }
}

876. 链表的中间结点_简单
仍然是快慢指针,慢指针每次移动1个位置,快指针每次移动2个位置,当快指针到链表尾部时,慢指针刚好处于链表中间。

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

判断链表是否有环

想象成2个人跑步,如果路线有环的话,两个人最终一定会相遇,如果没有环,那么跑的快的人会先到终点。
141. 环形链表_简单

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast.val == slow.val) {
                return true;
            }
        }
        return false;
    }
}

链表相交

160. 相交链表_简单
思路比较巧妙,如果两个链表长度一样,很显然从头结点往后走一定能相遇,但两个链表长度不一样时,短链表的指针走到相交节点时,长链表的指针还没有到相交节点。
处理方法就是让两个指针都走一次长短链表,这样路程就一样了,如果链表相交,就能找到相交的第一个节点,如果没相交,则会返回null。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA;
        ListNode pb = headB;
        while (pa != pb) {
            pa = pa == null ? headB : pa.next;
            pb = pb == null ? headA : pb.next;
        }
        return pa;
    }
}

链表合并

创建一个dummy节点,将满足条件的节点加入到dummy节点后面。
21. 合并两个有序链表_简单

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode p = new ListNode();
        ListNode head = p;
        while(l1 != null && l2 != null) {
            if (l1.val >= l2.val) {
                p.next = l2;
                l2 = l2.next;
                p = p.next;
            } else {
                p.next = l1;
                l1 = l1.next;
                p = p.next;
            }
        }
        if (l1 != null) {
            p.next = l1;
        }
        if (l2 != null) {
            p.next = l2;
        }
        return head.next;
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据