链表的知识（2）

今天继续和大家分享一周以来的收获，可能内容不是很多。

1.删除链表的倒数第N个结点

在输入之前我们是不知道是否会删除第一个结点的，为了不对第一个节点做特殊的判断，我们可以再定义一个结点，让这个结点指向头结点，这样我们就不用再对第一个结点进行特殊的判断。

struct ListNode* dummy = malloc(sizeof(struct ListNode));
dummy->val = 0,；
dummy->next = head;

第一个方法是遍历。

1.我们先遍历整个链表，计算他的链表长度。

2.从尾结点开始计数一直到倒数第n个为止。

接下来我们看一看代码：

int getLength(struct ListNode* head)
{
    int length = 0;
    while (head) 
    {
        ++length;
        head = head->next;
    }
    return length;
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) 
{
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0,；
    dummy->next = head;
    int length = getLength(head);
    struct ListNode* cur = dummy;
    for (int i = 1; i < length - n + 1; ++i) {
        cur = cur->next;
    //cur指向倒数第n+1个结点。
    }
    cur->next = cur->next->next;
    struct ListNode* ans = dummy->next;
    return ans;
}

2.两数相加

由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。

我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2，进位值为carry，则它们的和为n1+n2+carry；其中，答案链表处相应位置的数字为(n1+n2+carry)mod10，而新的进位值为 (n1+n2+carry) / 10。

如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个0 。

此外，如果链表遍历结束后，有carry>0，还需要在答案链表的后面附加一个节点，节点的值为carry。

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) 
{
    struct ListNode *head = NULL, *tail = NULL;
    int carry = 0;
    while (l1 || l2) {
        int n1 = l1 ? l1->val : 0;
        int n2 = l2 ? l2->val : 0;
        int sum = n1 + n2 + carry;
        if (!head) {
            head = tail = malloc(sizeof(struct ListNode));
            tail->val = sum % 10;
            tail->next = NULL;
        } else {
            tail->next = malloc(sizeof(struct ListNode));
            tail->next->val = sum % 10;
            tail = tail->next;
            tail->next = NULL;
        }
        carry = sum / 10;
        if (l1) {
            l1 = l1->next;
        }
        if (l2) {
            l2 = l2->next;
        }
    }
    if (carry > 0) {
        tail->next = malloc(sizeof(struct ListNode));
        tail->next->val = carry;
        tail->next->next = NULL;
    }
    return head;
}

以上是这些题的解法，如有错误，请多多指教。