• 两个链表求和的问题

    如果两个链表长度不同，那么短的链表在求和的时候，需要补0。

    如果两个链表长度相同，那么就比较每一位，相加，如果大于9，则进位，否则不进位。

    这里我们的想法是申请一个新的链表,如果两个链表长度不同，那么短的链表在求和的时候，需要补0。

    如果两个链表长度相同，那么就比较每一位，相加，如果大于9，则进位，否则不进位。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode dum = new ListNode(0);
            ListNode p1 = l1;
            ListNode p2 = l2;
            int carrier = 0 ; //进位
            ListNode cur = dum;    //
            while(p1!=null || p2!=null||carrier!=0){//一种极端的情况是如果两个链表都已经为空,这时候我们需要判断carrier是否为0
                //这里不能使用cur.val域
                int sum = (p1 != null?p1.val:0) + (p2 != null?p2.val:0) + carrier;
                carrier = sum /10;
                int digital = sum%10; //ListNode使用当前的值来一会进行申请新的值
                cur.next = new ListNode(digital);
                //为了能够使得链表继续往下走我们需要判断会进行延长链表
                if(p1!=null) p1 = p1.next;
                if(p2!=null) p2 = p2.next;
                cur = cur.next;
            }
            return dum.next;
        }
    }
    记得预设pre节点,方便从头遍历
  • 删除链表的倒数第N个节点

    最初的想法是使用一个反转链表,在正序的基础上进行删除链表,但是在删除链表的时候我们首先要进行考虑的是不能破坏链表的原本结构
    这时候我们的通用的想法是新增一个新的链表来进行表示
    1
    2
    3
    ListNode p1 = reverse(head);
    int count = 1;
    ListNode dummy = new ListNode(0);
    在这里我们可以进行设置两个指针,其中的一个指针用来寻找位置,另外的一个指针用来删除其中的节点
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode p1 = reverse(head);
            int count = 1;
            ListNode dummy = new ListNode(0); // 创建一个虚拟节点，方便处理头节点的情况
            dummy.next = p1;
            ListNode p2 = dummy; // p2是p1的前驱节点
            while(p1!=null){
                if(count == n){
                    p2.next = p1.next;
                }
                count++;
                p2 = p1; // 更新p2
                p1 = p1.next; // 更新p1
            }
            return reverse(dummy.next); // 反转回来，返回删除了倒数第n个节点的链表
        }
        public ListNode reverse(ListNode head){
            ListNode pre = null;
            ListNode cur = head;
            while(cur!=null){
                ListNode tmp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
            }
            return pre; // 返回反转后的链表的头节点
        }     
    }