[数据结构与算法]链表的汇总-习题

一:回顾
二:编程

一:

1.cur.next 保存下一个节点的地址
2.cur = cur.next 从当前的节点,走向下一个节点
3.while (cur != null) 链表遍历完了
4.while (cur.next != null) cur指向最后一个节点

?

二:
1. 遍历一次链表,删除其数字:
?? ?~定义一个前驱prev, prev.next = cur.next

2.反转一个链表:
?? ?~把head置空,在反头插法 ~cur = head.next ,head = null? ~循环 curN = cur.next, cur.next = head, head = cur, cur = cueN

3.返回链表中间节点:
?? ?~快慢指针 ~fast != null && fast.next != null

4.输入一个链表,输出该链表倒数第k个节点:
?? ?~快慢指针 ~让fast先走k步

5.环形链表:
?? ?~快慢指针 ~能相遇有环 ~在定义一个点从头走,然后与相遇的点一起走 相同的点 即为 环开始的点

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

6.给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/add-two-numbers
?? ?~就是相加,注意一下进制问题 ~这个题挺好解的,可是我当时一直在想用栈,队列什么的求

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int p = 0;
        while(l1 != null || l2 != null){
            int a = l1==null?0:l1.val;
            int b = l2==null?0:l2.val;
            int sum = a+b+p;

            p = sum /10;
            sum %= 10;

            cur.next = new ListNode(sum);
            cur = cur.next;

            if(l1 != null){
                l1 = l1.next;
            }
            if(l2 != null){
                l2 = l2.next;
            }

        }
        if(p == 1){
            cur.next = new ListNode(p);
        }
        return pre.next;
    }

7.删除总和为0的连续节点

??????? 搞一个傀儡头头,双层遍历

public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummyNode = new ListNode();
        dummyNode.next = head;
        ListNode pre = dummyNode;
        while(pre != null){
            ListNode p = pre.next;
            int sum = 0;
            while(p != null){
                sum += p.val;
                if(sum == 0){
                    pre.next = p.next;
                    break;
                }else {
                    p = p.next;
                }
            }
            if(p == null){
                pre = pre.next;
            }
        }
        return dummyNode.next;
    }

总结:

1.不要动头节点,否则,你修改之后,找不到链表了

2.有的时候定义一个傀儡头头,因为可能要删头节点

3.快慢指针很常用

4.要判断下一个节点,是否为空

5.单项的链表,可以定义前驱,后驱,以防找不到