在链表中查找无序元素

Question

给定除单个元素外按非降序排列的数字链表，找到单个不合适的元素。

我觉得必须有一个简单的算法，但我无法弄清楚。您实际上不能只是将当前数字与最后一个数字进行比较，因为您有像这样的情况 1、2、5、3、5，其中 3 将被错误地作为不合适的元素返回。

这是我的代码：

Node* fix(Node* head) {
if (!head || !head->next) return head;
Node* curr = head;
Node* prev = head;
Node* wrongNode = head;
Node* wrongPrev = head;

while (curr) {
if ((!curr->next && prev->val > curr->val) || //if at beginning or end, its outofplace
(curr == head && curr->val > curr->next->val)) {
wrongNode = curr;
wrongPrev = prev;
break;
}
if (curr->next && ((prev->val < curr->val && curr->next->val < curr->val) ||
(prev->val > curr->val && curr->next->val > curr->val))) { // if both sides of element are either larger or smaller, it might be outofplace. Check by running through the list to see if list is in correct order if you skip the element.
wrongNode = curr;
wrongPrev = prev;
Node* temp = head;
Node* tempPrev = head;
while (temp && tempPrev->val <= temp->val) {
tempPrev = temp;
if (temp->next == curr) temp = temp->next->next;
else temp = temp->next;
}
if (!temp) break;
}
prev = curr;
curr = curr->next;
}
if (wrongNode == head) head = wrongNode->next;
else wrongPrev->next = wrongNode->next;
curr = head, prev = head;

while (curr && wrongNode->val > curr->val) {
prev = curr;
curr = curr->next;
}
if (curr == head)   head = wrongNode;
else prev->next = wrongNode;
wrongNode->next = curr;
return head;
}

我基本上浏览了列表，如果我发现开头的元素大于下一个元素，或者末尾的元素小于前一个元素，则该元素一定是不合适的元素。

如果不是这种情况，我搜索一个元素 k，该元素在前后都有一个元素，使它们要么都大于 k，要么都比它小。然后，我尝试查看列表是否在没有 k 的情况下按非递减顺序排列。如果是，则 k 不合适。如果没有，那一定是下一个(我认为(。

然后我将 k 插入正确的位置。

有可能的输入，例如

1， 0，其中 1 或 0 不合适。

1、2、5、6、4、7，其中 4 不合适。

1、2、5、3、4，其中 5 不合适。

7、1、2，其中 7 不合适。

必须有一种更简单的方法来做到这一点。我只是没有看到它。

Answer 1

线性扫描列表，获取当前和先前元素的差异。如果差值为负数，则当前或上一个项目不合适。至少在您的情况下，可以通过试用删除"当前"来检查这一点。如果删除导致负差异的元素不能修复列表，则删除以前的必须。

List : 1  2  5  6  4  7
diff =    1  3  1 -2  3
Trial: 1  2  5  6  *  7 --> correct
1  2  5  *  4  7 --> incorrect (no need to check)
List : 7  1  2
diff :   -6  1
Trial: 7  *  2  --> incorrect
Trial: *  1  2  --> correct (no need to test)

Answer 2

假设

• 列表按非降序排列。
• 列表的长度大于2并且at most 1元素顺序不正确。

我已经尝试java.

链表的定义

class ListNode{
int data;
ListNode next;
ListNode(int d){
data = d;
next = null;
}
}

算法

• 循环访问元素列表。
• 现在，如果当前元素大于下一个元素-
  • 如果即使在下一个元素之后也存在一个元素，我们将比较窗口移动到current,next,next to next.
  • 如果下一个元素后存在no element，我们将比较窗口移动到prev,curr,next.

法典：

class ListNode{
int data;
ListNode next;
ListNode(int d){
data = d;
next = null;
}
}
public class Solution {
public static void main(String[] args) {
int[][] test = {
{1,2,5,3,5},
{1,2,5,1},
{1,2,5,2},
{7,1,2},
{1,2,5,6,4,7},
{1,2,3,4,5,6,7},
{1,2,5,3,4},
{1,2,5,3,5,6,7},
{1,2,5,3,4,4,4},
{2,3,2},
{3,3,2}
};
for(int i=0;i<test.length;++i){
ListNode head = new ListNode(test[i][0]);
ListNode temp = head;
for(int j=1;j<test[i].length;++j){
ListNode newNode = new ListNode(test[i][j]);
temp.next = newNode;
temp = newNode;
}
temp = findOutOfOrderElement(head);
System.out.println(temp == null ? "No out of place element" : temp.data);  
}        
}
private static ListNode findOutOfOrderElement(ListNode head){
ListNode ptr  = head;
ListNode prev = null;
while(ptr != null && ptr.next != null){
if(ptr.data > ptr.next.data){
if(ptr.next.next == null){
if(prev == null) return ptr;
if(prev.data > ptr.next.data) return ptr.next;
else return ptr;
}else{
if(ptr.data <= ptr.next.next.data) return ptr.next;
return ptr;
}
}
prev = ptr;
ptr= ptr.next;            
}
return null;
}
}

输出

3
1
5
7
4
No out of place element
5
3
5
3
2