Leetcode TOP100 ------ 链表

• 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

解题思路：跟踪进位，逐位相加

	public static ListNode add(ListNode l1, ListNode l2) {
	    ListNode dummyHead = new ListNode(0);
	    //初始化链表l1，l2，记录当前节点
	    ListNode p = l1, q = l2, curr = dummyHead;
	    //进位，只可能为0或1
	    int carry = 0;
	    //遍历链表l1，l2到末尾
	    while (p != null || q != null) {
	    	//节点不为空则取出节点值
	        int x = (p != null) ? p.val : 0;
	        int y = (q != null) ? q.val : 0;
	        //计算对应节点相加的和
	        int sum = carry + x + y;
	        //计算进位
	        carry = sum / 10;
	        curr.next = new ListNode(sum % 10);
	        curr = curr.next;
	        if (p != null) p = p.next;
	        if (q != null) q = q.next;
	    }
	    //检查 carry = 1carry=1 是否成立，如果成立，则向返回列表追加一个含有数字 11 的新结点。
	    if (carry > 0) {
	        curr.next = new ListNode(carry);
	    }
	    //返回头结点的下一个节点，因为头结点初始化为0，下一个节点才是插入的节点
	    return dummyHead.next;
	}

• 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

解题思路：双指针，一次遍历

	public ListNode removeNthFromEnd(ListNode head, int n) {
	    ListNode dummy = new ListNode(0);
	    dummy.next = head;
	    ListNode first = dummy;
	    ListNode second = dummy;
	    // 使第一个指针和第二个指针相隔n个
	    for (int i = 1; i <= n + 1; i++) {
	        first = first.next;
	    }
	    // 两个指针同时遍历，直到第一个指针到末尾
	    while (first != null) {
	        first = first.next;
	        second = second.next;
	    }
	    //删除第二个指针的下一个元素
	    second.next = second.next.next;
	    return dummy.next;
	}

总结：链表算法可以采用哑结点来进行辅助，哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。

------------------- 持续更新中 -------------------