java - 这个链表分区算法是如何工作的?
问题描述
我现在正在阅读《Cracking the Coding Interview 》一书,它提出了一个链表分区问题:
给定一个链表和一个值 x,围绕一个值 x 划分一个链表,使得所有小于 x 的节点都在所有大于或等于 x 的节点之前。
假设链表不为空。
该解决方案取自 GeeksForGeeks 网站,与 CTCI 书中提供的第二种解决方案相同:
// Function to make a new list // (using the existing nodes) and // return head of new list. static Node partition(Node head, int x) { /* Let us initialize start and tail nodes of new list */ Node tail = head; // Now iterate original list and connect nodes Node curr = head; while (curr != null) { Node next = curr.next; if (curr.data < x) { /* Insert node at head. */ curr.next = head; head = curr; } else // Append to the list of greater values { /* Insert node at tail. */ tail.next = curr; tail = curr; } curr = next; } tail.next = null; // The head has changed, so we need // to return it to the user. return head; }
我不明白这个解决方案。这个算法是如何工作的?为什么是正确的?
解决方案
试着这样想:
假设这是我们的链表(0) -> (1) -> (2) -> (-1) -> (1) -> (-5)
(显然链表看起来不像这样,但对于我们的示例)
和x = 0
我们这样next = curr.next
做是为了不“丢失”下一个节点
\ 我要标记 *head 和 ^tail
现在我们看 (0) 它是否小于 x 并不重要(bcs 它的头部和尾部)所以它的指针指向自身
[*^(0)< ] [ (1) -> (2) -> (-1) -> (1) -> (-5) ]
现在我们看 (1) 它也不小于 x 所以 (0) 指向它并且它变成 ^tail
[ *(0) -> ^(1)< ] [ (2) -> (-1) -> (1) -> (-5) ]
(附上这两个列表,但让我们想象一下它们不是)
同样的事情发生在 (2) ^tail 上,即 (1) 指向它
[ *(0) -> (1) -> ^(2)< ] [ (-1) -> (1) -> (-5) ]
现在我们看 (-1) 但是这次它小于 x 所以它设置为指向 *head 然后设置为 *head
[ *(-1) -> (0) -> (1) -> ^(2)< ] [ (1) -> (-5) ]
等等:
[ *(-1) -> (0) -> (1) -> (2) -> ^(1)< ] [ (-5) ]
[ *(-5) -> (-1) -> (0) -> (1) -> (2) -> ^(1)< ] [ ]
推荐阅读
- java - 如何添加 - 登录 printf
- jquery - 像画布中的垂直弧线一样的文本
- java - 如何在 Spring Security 中通过电子邮件而不是用户名登录
- javascript - 如何在产品列表仍在 prestashop 中加载时显示加载图像
- mysql - 在所有列mysql上添加唯一约束的成本是多少
- python - 在数据框条目中搜索字符串并将其复制 python
- asp.net - 如何使用 LINQ 从 Datatable 中获取过滤后的数据集
- ms-access - 使用 Select Distinct 并编辑第二列中的输出
- c# - 类库自动添加到 Visual Studio 7.5.2 mac os X 中的其他项目
- html - google siganute 使一张图片有两个链接