20191215一周算法学习总结

本周,重温算法中关于单链表的内容,主要涉及:

  1. 用Swift实现了单/双链表
  2. 用C实现单链表的一些常见操作

Swift实现单双链表

实现了类似Array的 count,empty,insert,remove等操作。
因为Array使用的是struct,考虑以后使用struct将链表再实现一遍。 代码参见:Swift: linked list

单链表常见操作

Leetcode上的常见单链表操作。 原本想都用 Swift 实现,但只有部分题可以使用 Swift 提交,于是还是以 C 为主。

单链表反转 206

入门级的算法题,主要步骤:初始化前驱节点为 null 和当前节点为头节点,将当前节点的 next 设置为前驱节点。 然后,当前节点和前驱节点一起向后移动,重复操作,直到当前节点为 null。

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *prev = NULL;
    struct ListNode *current = head;
    struct ListNode *next = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

反转类的题目,可以画分布示意图,再将操作一步一步用代码描述出来。

链表中间节点 876

Swift 实现,注意 optional 的运用。

func middleNode(_ head: ListNode?) -> ListNode? {
        var list1: ListNode? = head
        var list2: ListNode? = head
        while let list2Next = list2?.next,  (list2 != nil) {
            list1 = list1?.next
            list2 = list2Next.next
        }
        return list1
    }

提交后结果显示内存使用较多,待优化。

单链表回文判断 234

判断回文首先需要准备两个指针设为A和B(常见的说法为快满指针),A每次移动一步,B每次移动两步,直到 B 移动到末端。如果链表节点数为偶数,此时 A 指针位于中间节点;如果节点数为奇数, A 指针位于中心左侧。将 A 指针右移,此时 A 指针就指向下半段链表。然后从 header 和 A 开始向后逐一比较,直到 A 指向 null。

struct ListNode* reverseList(struct ListNode *list){
    struct ListNode *prev = NULL;
    struct ListNode *current = list;
    struct ListNode *next = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

bool isPalindrome(struct ListNode* head){
    if (head == NULL) {
        return true;
    }
    if (head->next == NULL) {
        return true;
    }
    struct ListNode *list1 = head;
    struct ListNode *list2 = head;
    while (list2->next != NULL && list2->next->next) {
        list1 = list1->next;
        list2 = list2->next->next;
    }
    list2 = list1->next;
    list1->next = NULL;
    struct ListNode *reversed = reverseList(list2);
    while (reversed != NULL) {
        if (head->val == reversed->val) {
            reversed = reversed->next;
            head = head->next;
        }else {
            return false;
        }
    }
    return true;
}

这里需要注意,后半段反转后和前半段去比较的时候,前半段长度可能比后半度多1。因此,只需要比较后半段链表长度节点是否都相等即可。

合并两个有序链表 21

题目描述:

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    // if (l1 == NULL)
    // {
    //     return l2;
    // }
    // if (l2 == NULL)
    // {
    //     return l1;
    // }

    struct ListNode *sorted = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *sortedList = sorted;
    while(l1 != NULL && l2 != NULL){
        if (l1->val < l2->val)
        {
            sorted->next = l1;
            l1 = l1->next;
        }else {
            sorted->next = l2;
            l2 = l2->next;
        }
        sorted = sorted->next;
    }
    if (l1 != NULL)
    {
        sorted->next = l1;
    }else {
        sorted->next = l2;
    }

    return sortedList->next;

}

总结: 开始几行注释的代码多余; 生成 sorted 哨兵节点,来简化操作

删除单链表倒数第N个节点 19

题目:

Given a linked list, remove the n-th node from the end of list and return its head. Given n will always be valid. Could you do this in one pass?

注意,这里的 n 始终是有效的,所以实现的时候不要再做有效性的判断了。另外,n 的取值是从1开始的。
直接的解法可以先遍历一遍求出长度,再计算对应正向第 m 个。如果要求只遍历一次的话,借鉴回文题解中快慢指针的思想,可以设置两个相隔 n 长度的指针,当后一个到节点尾部的时候,前一个就是待删除的节点。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode* slow = dummy;
    struct ListNode* fast = dummy;
    int i = 0;
    while( i <= n){
        fast = fast->next;
        i++;
    }
    if (fast == NULL){
        return head->next;
    }
    while(fast != NULL){
        slow = slow->next;
        fast = fast->next;
    }
    slow->next = slow->next->next;
    return head;
}

简单的示意图如下,注意 “o” 表示哨兵节点 dummy :

->o->node->node->node->node->node->null
     ______________
    |______________|

方块向右逐一移动直到链尾。
总结:
这里还是利用了哨兵节点,因为前提有 n 始终有效,从哨兵节点开始算起的话,就不需要去考虑边界条件--删除倒数第链表长度个节点。