【Cracking the Code Interview(5th edition)】二、链表(C++)

链表结点类型定义：

 class Node {

 public:

     int data = ;

     Node *next = nullptr;

     Node(int d) {

         data = d;

     }

 };

快行指针(runner)技巧：

同时使用两个指针来迭代访问链表，其中一个比另一个超前一些。快指针比慢指针先行几步或者快指针与慢指针的速度呈一定的关系。

dummy元素技巧：

在链表头部添加一个哑结点，通常可以简化首部或尾部的特殊情况的处理。

2.1 编写代码，移除未排序链表中的重复结点。

进阶：如果不得使用临时缓冲区，该怎么解决？

解答：如果可以使用临时缓冲区，那么可以建立一个Hash表，保存已出现的结点内容，遍历过程中如果发现重复元素，就删除该结点。

 void deleteDups(Node *head) {

     if (head == nullptr) return;

     unordered_set<int> table;

     Node *f = head, *p = head->next;

     table.insert(head->data);

     while (p != nullptr) {

         if (table.find(p->data) == table.end()) {

             table.insert(p->data);

             f = p;

             p = p->next;

         }

         else {

             f->next = p->next;

             delete p;

             p = f->next;

         }

     }

 }

如果不允许使用额外的数组，则暴力解决..

 void deleteDups(Node *head) {

     if (head == nullptr || head->next == nullptr) return;

     Node *f = head, *p = head->next;

     while (p != nullptr) {

         Node *pc = head;

         while (pc != p) {

             if (pc->data == p->data) {

                 f->next = p->next;

                 delete p;

                 p = f;

                 break;

             } else {

                 pc = pc->next;

             }

         }

         p = p->next;

     }

 }

2.2 实现一个算法，找出单向链表中倒数第k个结点。

解答：利用快行指针技巧，让快指针先走k步，然后同步地挪动快慢指针，快指针到达链表尾时，慢指针恰好指向倒数第k个结点。(剑指offer上也有这道题)

 Node * kthToLast(Node *head, int k) {

     if (k < ) return nullptr;

     Node *p1 = head, *p2 = head;

     for (int i = ; i < k - ; ++i) {

         if (p2 == nullptr || p2->next == nullptr)

             return nullptr;

         p2 = p2->next;

     }

     while (p2->next != nullptr) {

         p1 = p1->next;

         p2 = p2->next;

     }

     return p1;

 }

2.3 实现一个算法，删除单链表中的某个结点，假定你只能访问该结点。

解答：本题的意思是我们不知道链表的首结点位置。那么删除该结点的方法是：将其后继结点的值赋给该节点，然后删除后继结点。有一个问题是：如果给定的结点指针是空指针或是最后一个指针时会出错，我们可以通过程序的返回值来指明错误或抛出异常。

 bool deleteNode(Node *node) {

     if (node == nullptr || node->next == nullptr) {

         return false;

     }

     Node *next = node->next;

     node->data = next->data;

     node->next = next->next;

     delete next;

     return true;

 }

2.4 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之间。

解答：维护两个链表，分别保存大于x和小于x的元素，然后将两个链表连接起来。尾插法可以保持元素的相对位置。加入dummy结点可以简化代码。Leetcode上也有这道题。

 Node * partition(Node *head, int x) {

     Node dummy_left(-), dummy_right(-);

     Node *pl = &dummy_left, *pr = &dummy_right;

     for (Node * p = head; p != nullptr; p = p->next) {

         if (p->data < x) {

             pl->next = p;

             pl = pl->next;

         } else {

             pr->next = p;

             pr = pr->next;

         }

     }

     pl->next = dummy_right.next;

     pr->next = nullptr;

     return dummy_left.next;

 }

2.5 给定两个用链表表示的整数，每个结点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。

进阶：假设这些数位是正向存放的，请再做一遍。

反向表示举例：(Leetcode)

7->1->6

5->9->2->1

___________________

2->1->9->1

 Node * addList(Node *l1, Node *l2) {

     Node dummy(-);

     Node *p = &dummy;

     int carry = ;    //进位

     while (l1 != nullptr || l2 != nullptr) {

         int v = ;

         if (l1 != nullptr) {

             v += l1->data;

             l1 = l1->next;

         }

         if (l2 != nullptr) {

             v += l2->data;

             l2 = l2->next;

         }

         v += carry;

         carry = v / ;

         v = v % ;

         Node *node = new Node(v);

         p->next = node;

         p = p->next;

     }

     if (carry > ) {

         Node * node = new Node(carry);

         p->next = node;

         p = p->next;

     }

     return dummy.next;

 }

进阶问题：可以借助一个栈实现，或者先通过填零把两个链表的长度变为一致，然后递归求解。以下是后一种思路的代码：(partialSum是一个包裹类，把一个Node指针和一个表示进位的int捆绑在一起，方便函数返回)。把独立的处理逻辑分列到不同的函数中，使代码思路清晰，可读性强。

 class partialSum {

 public:

     Node * node = nullptr;

     int carry = ;

 };

 int length(Node *l) {

     int len = ;

     while (l != nullptr) {

         ++len;

         l = l ->next;

     }

     return len;

 }

 Node * padList(Node *l, int n) {

     //填零

     Node * new_head = l;

     for (int i = ; i < n; ++i) {

         Node *node = new Node();

         node->next = l;

         new_head = node;

     }

     return new_head;

 }

 partialSum * addListHelper(Node *l1, Node *l2) {

     partialSum *sum = new partialSum;

     if (l1->next == nullptr && l2->next == nullptr) {

         int v = l1->data + l2->data;

         sum->node = new Node(v % );

         sum->carry = v / ;

         return sum;

     }

     else {

         partialSum *part_sum = addListHelper(l1->next, l2->next);

         int v = l1->data + l2->data + part_sum->carry;

         sum->node = new Node(v % );

         sum->carry = v / ;

         sum->node->next = part_sum->node;

     }

     return sum;

 }

 Node * addList(Node *l1, Node *l2) {

     int len1 = length(l1);

     int len2 = length(l2);

     if (len1 < len2)

         l1 = padList(l1, len2 - len1);

     else if (len1 > len2)

         l2 = padList(l2, len1 - len2);

     if (l1 == nullptr && l2 == nullptr)

         return nullptr;

     partialSum *sum = addListHelper(l1, l2);

     if (sum->carry > ) {

         Node *node = new Node(sum->carry);

         node->next = sum->node;

         return node;

     } else return sum->node;

 }

2.6 给定一个有环链表，实现一个算法返回环路的开头结点。

解答：链表环图示：

第一种方法：类似于找一个数组或链表中的重复元素的问题，这里实际上要找一个链表中next指针的重复问题(也可以与head重复)。所以同样可以用hash表解决，但是需要一定的额外存储空间。

 Node * findLoopBeginning(Node *head) {

     unordered_set<Node *> table;

     while (head != nullptr) {

         if (table.find(head) != table.end()) {

             return head;

         } else {

             table.insert(head);

             head = head->next;

         }

     }

     return nullptr;

 }

第二种方法：如果不允许用额外的数组空间，那么还有另一种技巧性比较强的方法：快慢指针法。

首先：如何判断是否有环？定义两个指针fast和slow，以不同的速度遍历链表。fast每次走两步，slow每次走一步，这样如果链表存在环，则两个指针一定会相遇。而且相遇的位置在环内。

然后：环入口点怎么找？当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：
2s = s + nr
s= nr
设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)
(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

 Node * findCircleBeginning(Node *head) {

     Node *fast = head, *slow = head;

     while (fast && fast->next) {

         fast = fast->next->next;

         slow = slow->next;

         if (fast == slow) {

             break;

         }

     }

     if (fast == nullptr || fast->next == nullptr) {

         return nullptr;

     }

     slow = head;

     while (slow != fast) {

         slow = slow->next;

         fast = fast->next;

     }

     return slow;

 }

2.7 编写一个函数，检查链表是否是回文(正看反看相同)。

解答：

方法1：反转链表，判断与原链表是否一致，实际上只需判断两个链表的前面一半即可。

方法2：反转链表的前半部分，与后半部分比较，借助栈来实现。

 bool isPalindrome(Node *list) {

     Node *fast = head, *slow = head;

     stack<int> s;

     while (fast != nullptr && fast->next != nullptr) {

         s.push(slow->data);

         slow = slow->next;

         fast = fast->next->next;

     }

     if (fast != nullptr) {

         slow = slow.next;

     }

     while (slow != nullptr) {

         if (s.top() != slow->data) {

             return false;

         }

         slow = slow->next;

     }

     return true;

 }

方法3：递归，逐层判断收尾对应元素是否相等。如：0(1(2(3)2)1)0。

 class Result {

 public:

     Node *node = nullptr;    //该段后接的第一个结点

     bool result = false;    //该段是否满足回文性质

 };

 Result isPalindromeRecurse(Node *list, int length) {

     Result ret;

     if (length <= ) {

         ret.result = true;

     }

     else if (length == ) {

         ret.node = list->next;

         ret.result = true;

     }

     else if (length == ) {

         ret.node = list->next->next;

         ret.result = (list->data == list->next->data);

     }

     else {

         Result part_ret = isPalindromeRecurse(list->next, length - );

         if (part_ret.result == false) {

             ret.node = nullptr;

             ret.result = false;

         }

         else {

             ret.node = part_ret.node->next;

             ret.result = (list->data == part_ret.node->data);

         }

     }

     return ret;

 }

 bool isPalindrome(Node *list) {

     return isPalindromeRecurse(list, length(list)).result;

 }

巴特西

【Cracking the Code Interview(5th edition)】二、链表(C++)

最新文章

热门文章