about 10 results (0.02 seconds)

Linked List - Linked List Cycle II

by LauCyun Sep 22,2014 15:30:42 5,099 views

Question

Problem Statement

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Example

Given1->2->3->4->5->6, tail connects to node index 2, return 3.

题解 - 快慢指针

这题 Linked List - Linked List Cycle 的升级版,首先假设组成环的节点个数为\(r\),链表中节点个数为\(n\)

首先我们来分析下在链表有环时都能推出哪些特性:

  1. 快慢指针第一次相遇时快指针比慢指针多走整数个环, 这个容易理解,相遇问题。
  2. 每次相遇都在同一个节点。第一次相遇至第二次相遇,快指针需要比慢指针多走一个环的节点个数,而快指针比慢指针多走的步数正好是慢指针自身移动的步数,故慢指针恰好走了一圈回到原点。

从以上两个特性可知,在仅仅知道第一次相遇时的节点还不够,相遇后如果不改变既有策略则必然找不到环的入口。

接下来我们分析如何从第一次相遇的节点走到环的入口节点。还是先从实际例子出发,以下图为例:

slowfast节点分别初始化为节点12,假设快慢指针第一次相遇的节点为\( C_i\),那么此时慢指针正好走了\(n-r+i-1\)步,快指针则走了\(2(n-r+i-1)\)步,快慢指针第一次相遇时慢指针肯定没有走完整个环,且慢指针走的步数即为整数个环节点个数,由性质1和性质2可联合推出:

\((n-r+i-1)+1=x \cdot r\)  (\(x\)为非负整数)      式1

为什么在后面加1?是因为快指针初始化时多走了一步

现在分析下相遇的节点和环的入口节点之间的关联,要从环中第i个节点走到环的入口节点,则按照顺时针方向移动的节点数:

\(x \cdot r - i+1\)    (\(x\)为非负整数)             式2

由式1可以推知:\(n-r=x \cdot r-i\),也就是说从头节点走到环的入口节点所走的步数\(n-r\)

如果快慢指针第一次相遇时让快指针从头节点出发,慢指针仍从当前位置迭代,为了让快慢指针在环的入口点相遇,由式1和式2可以推知:需要让慢指针先走一步,否则会出现死循环。

C:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/**
 * @param head: The first node of linked list.
 * @return: The node where the cycle begins.
 *          if there is no cycle, return null
 */
struct ListNode *detectCycle(struct ListNode *head) {
    if (NULL == head || NULL == head->next) {
        return NULL;
    }

    struct ListNode *slow = head, *fast = head->next;
    while (NULL != fast && NULL != fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            slow = slow->next;
            fast = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return fast;
        }
    }
    return NULL;
}

源码分析

  1. 异常处理。
  2. 找第一次相遇的节点。
  3. 先将slow先走一步,然后将fast置为头节点,并只走一步,直至快慢指针第二次相遇,返回慢指针所指的节点。

复杂度分析

第一次相遇的最坏时间复杂度为\( O(n)\),第二次相遇的最坏时间复杂度为\( O(n)\),故总的时间复杂度近似为\( O(n)\),空间复杂度\( O(1)\)

Reference

...

Tags Read More..


Linked List - Linked List Cycle

by LauCyun Sep 22,2014 10:01:24 6,235 views

Question

Problem Statement

Given a linked list, determine if it has a cycle in it.

Example

Given1->2->3->4->5, tail connects to node index 1, return true.

题解 - 快慢指针

对于带环链表的检测,效率较高且易于实现的一种方式为使用快慢指针。快指针每次走两步,慢指针每次走一步,如果快慢指针相遇(快慢指针所指内存为同一区域)则有环,否则快指针会一直走到NULL为止退出循环,返回false

快指针走到NULL退出循环即可确定此链表一定无环这个很好理解。那么带环的链表快慢指针一定会相遇吗?先来看看下图。

在有环的情况下,最终快慢指针一定都走在环内,加入第i次遍历时快指针还需要k步才能追上慢指针,由于快指针比慢指针每次多走一步。那么每遍历一次快慢指针间的间距都会减少1,直至最终相遇。故快慢指针相遇一定能确定该链表有环。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef enum { false, true } bool;

/**
 *
 * @param head: The first node of linked list.
 * @return: True if it has a cycle, or false
 */
bool hasCycle(struct ListNode *head) {
    if (NULL == head || NULL == head->next) {
        return false;
    }

    struct ListNode *slow = head, *fast = head;
    while (NULL != fast && NULL != fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            return true;
        }
    }
    return false;
}

源码分析

  1. 异常处理,将head->next也考虑在内有助于简化后面的代码。
  2. 慢指针初始化为head, 快指针初始化为head的下一个节点,这是快慢指针初始化的一种方法,有时会简化边界处理,但有时会增加麻烦,比如该题的进阶版。

复杂度分析

  1. 在无环时,快指针每次走两步走到尾部节点,遍历的时间复杂度为\( O(\frac{n}{2})\).
  2. 有环时,最坏的时间复杂度近似为 \(O(n)\). 最坏情况下链表的头尾相接,此时快指针恰好在慢指针前一个节点,还需 n 次快慢指针相遇。最好情况和无环相同,尾节点出现环。

故总的时间复杂度可近似为\(O(n)\).

Reference

...

Tags Read More..


Linked List - Remove Nth Node From End of List

by LauCyun Sep 20,2014 13:46:17 3,637 views

Question

Problem Statement

Given a linked list, remove the nth node from the end of list and return its head.

  •  Notice
    The minimum number of nodes in list is n.

Example

Given linked list: 1->2->3->4->5->null, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5->null.

题解

简单题, 使用快慢指针解决此题,需要注意最后删除的是否为头节点。让快指针先走n步,直至快指针走到终点,找到需要删除节点之前的一个节点,改变slow->next域即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/**
 * Remove Nth Node From End of List.
 *
 * @param head: The first node of linked list.
 * @param n: An integer.
 * @return: The head of linked list.
 */
struct ListNode *
removeNthFromEnd(struct ListNode *head, const int n) {
    if (head == NULL || n < 0) {
        return NULL;
    }

    struct ListNode *fast = head;
    struct ListNode *slow = head;

    int i = 0;
    while (i < n) {
        if (fast == NULL) {
            return NULL;
        }
        fast = fast->next;
        ++i;
    }
    if (fast == NULL) {
        return head->next;
    }

    while (fast->next != NULL) {
        slow = slow->next;
        fast = fast->next;
    }

    slow->next = slow->next->next;
    return head;
}

以上代码单独判断了是否需要删除头节点的情况,在遇到头节点不确定的情况下,引入dummy节点将会使代码更加优雅,改进的代码如下。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/**
 * Remove Nth Node From End of List.
 *
 * @param head: The first node of linked list.
 * @param n: An integer.
 * @return: The head of linked list.
 */
struct ListNode *
removeNthFromEnd(struct ListNode *head, const int n) {
    if (head == NULL || n < 0) {
        return NULL;
    }

    struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val = -1;
    dummy->next = head;
    struct ListNode *curr = dummy;

    int i = 0;
    while (i < n) {
        if (head == NULL) {
            return NULL;
        }
        head = head->next;
        ++i;
    }

    while (head != NULL) {
        head = head->next;
        curr = curr->next;
    }

    curr->next = curr->next->next;
    head = dummy->next;
    free(dummy);
    return head;
}

...

Tags Read More..


Linked List - Add Two Numbers

by LauCyun Sep 20,2014 12:58:04 5,030 views

Question

Problem Statement

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Given 7->1->6 + 5->9->2. That is, 617 + 295.

Return 2->1->9. That is 912.

Given 3->1->5 and 5->9->2, return 8->0->8.

题解

一道看似简单的进位加法题,实则杀机重重,不信你不看答案自己先做做看。

首先由十进制加法可知应该注意进位的处理,但是这道题仅注意到这点就够了吗?还不够!因为两个链表长度有可能不等长!因此这道题的亮点在于边界和异常条件的处理,感谢 @wen 引入的 dummy 节点,处理起来更为优雅!

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/***
 * Create a new list node.
 * @param val: The value of the new node.
 * @return
 */
struct ListNode *
newNode(const int val) {
    struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    temp->next = NULL;
    return temp;
}

/***
 * You are given two non-empty linked lists representing two non-negative integers.
 * The digits are stored in reverse order and each of their nodes contain a single digit.
 * Add the two numbers and return it as a linked list.
 * You may assume the two numbers do not contain any leading zero, except the number 0 itself.
 *
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 *
 * @param l1: linked lists.
 * @param l2: linked lists.
 * @return: a linked lists.
 */
struct ListNode *
addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {
    if (l1 == NULL && l2 == NULL) {
        return NULL;
    }
    struct ListNode *dummy = newNode(-1);
    struct ListNode *curr = dummy;
    int carry = 0;
    while ((l1 != NULL) || (l2 != NULL) || (carry > 0)) {
        int l1_val = (l1 != NULL) ? l1->val : 0;
        int l2_val = (l2 != NULL) ? l2->val : 0;
        int sum = carry + l1_val + l2_val;

        carry = (int) (sum / 10);
        curr->next = newNode(sum % 10);

        curr = curr->next;
        if (l1 != NULL) l1 = l1->next;
        if (l2 != NULL) l2 = l2->next;
    }
    curr = dummy->next;
    free(dummy);
    return curr;
}

源码分析

  1. 迭代能正常进行的条件为(l1 != NULL) || (l2 != NULL) || (carry > 0), 缺一不可。
  2. 对于空指针节点的处理可以用相对优雅的方式处理 - int l1_val = (l1 != NULL) ? l1->val : 0;
  3. 生成新节点时需要先判断迭代终止条件(l1 == NULL) && (l2 == NULL) && (carry <= 0), 避免多生成一位数0。 使用 dummy 节点可避免这一情况。

复杂度分析

没啥好分析的,时间和空间复杂度均为\(O(max(L1, L2))\)

...

Tags Read More..


Linked List - Partition List

by LauCyun Sep 19,2014 14:57:44 3,768 views

Question

Problem Statement

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example

Given 1->4->3->2->5->2 and x = 3,

return 1->2->2->4->3->5.

题解

此题出自 CTCI 题 2.4,依据题意,是要根据值x对链表进行分割操作,具体是指将所有小于x的节点放到不小于x的节点之前,咋一看和快速排序的分割有些类似,但是这个题的不同之处在于只要求将小于x的节点放到前面,而并不要求对元素进行排序。

这种分割的题使用两路指针即可轻松解决。左边指针指向小于x的节点,右边指针指向不小于x的节点。由于左右头节点不确定,我们可以使用两个dummy节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/***
 * Create a new list node.
 * @param val: The value of the new node.
 * @return
 */
struct ListNode *
newNode(const int val) {
    struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    temp->next = NULL;
    return temp;
}

/***
 * Given a linked list and a value x,
 * partition it such that all nodes less than x come before nodes greater than or equal to x.
 *
 * For example
 *   Given 1->4->3->2->5->2 and x = 3,
 *   return 1->2->2->4->3->5.
 *
 * @param head: The linked list of headers.
 * @param x: a value x.
 * @return: The linked list of headers.
 */
struct ListNode *
partition(struct ListNode *head, const int x) {
    if (head == NULL) {
        return NULL;
    }

    struct ListNode *leftDummy = newNode(-1);
    struct ListNode *left = leftDummy;
    struct ListNode *rightDummy = newNode(-1);
    struct ListNode *right = rightDummy;
    struct ListNode *curr = head;
    while (curr != NULL) {
        if (curr->val < x) {
            left->next = curr;
            left = left->next;
        } else {
            right->next = curr;
            right = right->next;
        }
        curr = curr->next;
    }

    // post-processing
    right->next = NULL;
    left->next = rightDummy->next;
    free(rightDummy);

    head = leftDummy->next;
    free(leftDummy);
    return head;
}

源码分析

  1. 异常处理
  2. 引入左右两个dummy节点及leftright左右尾指针
  3. 遍历原链表
  4. 处理右链表,置right->next为空(否则如果不为尾节点则会报错,处理链表时 以 null 为判断),将右链表的头部链接到左链表尾指针的next,返回左链表的头部

其主要过程如下图:

复杂度分析

遍历链表一次,时间复杂度近似为\(O(n)\) ,使用了两个dummy节点及中间变量,空间复杂度近似为\(O(1)\)

...

Tags Read More..