判断单链表是否递增有序

单链表是一种常见的数据结构，由节点和指针组成，每个节点存储数据和指向下一个节点的指针。判断单链表是否递增有序是一个基本的算法问题，本文将从多个角度进行分析。

一、问题描述

给定一个单链表，判断链表中的节点是否按照递增顺序排列。例如，链表 1→2→3→4 是递增有序的，而链表 1→3→2 则不是递增有序的。

二、算法思路

判断单链表是否递增有序的算法主要有两种思路：迭代和递归。

迭代算法的思路是，从头节点开始遍历链表中的每个节点，判断当前节点的值是否小于上一个节点的值，如果不是，则说明链表不是递增有序的。

递归算法的思路是，判断当前节点的值是否小于下一个节点的值，并且递归判断下一个节点。

三、实现方法

1.迭代思路的实现方法：

```python

def is_sorted(head):

if not head:

return True

pre = head.value

cur = head.next

while cur:

if cur.value < pre:

return False

pre, cur = cur.value, cur.next

return True

```

2.递归思路的实现方法：

```python

def is_sorted(head):

if not head or not head.next:

return True

if head.value > head.next.value:

return False

return is_sorted(head.next)

```

四、算法复杂度分析

迭代算法的时间复杂度为 O(n)，空间复杂度为 O(1)；递归算法的时间复杂度为 O(n)，空间复杂度为 O(n)。因此，在空间复杂度上，迭代算法更优。

五、测试用例

以下是本算法的测试用例：

```python

class TestSolution(unittest.TestCase):

def test_is_sorted(self):

head1 = Node(1)

node1 = Node(2)

node2 = Node(3)

node3 = Node(4)

head1.next = node1

node1.next = node2

node2.next = node3

self.assertEqual(is_sorted(head1), True)

head2 = Node(1)

node4 = Node(3)

node5 = Node(2)

head2.next = node4

node4.next = node5

self.assertEqual(is_sorted(head2), False)

```

六、结论

本文对判断单链表是否递增有序的问题进行了分析，提出了两种算法思路：迭代和递归。在实现方法和复杂度分析方面进行了讨论，并给出了测试用例。