pta6-2 求链式表的表长

pta6-2 题目通常是指某个编程题目，涉及到链表数据结构，这里的"求链式表的表长"指的是计算给定单向链表中节点的数量。在链表中，每个节点都有一个指向下一个节点的指针，所以要找到链表的长度，你需要从头开始遍历链表，直到遇到`null`（表示链表结束），计数器加一，最后返回计数器的值即为链表的长度。

这个过程可以使用递归或迭代的方式来实现。下面是基本的迭代算法示例：

def getLinkedListLength(head):
    if head is None:
        return 0
    else:
        length = 1  # 初始化长度为1，因为已知有一个节点
        current = head.next  # 赋值当前节点为头节点的下一个节点
        while current is not None:
            length += 1
            current = current.next
        return length

# 或者使用递归版本
def getLinkedListLengthRecursive(head):
    if head is None:
        return 0
    else:
        return 1 + getLinkedListLengthRecursive(head.next)

这里假设`head`是链表的头节点，`head.next`是第二个节点，依此类推。

相关问题

用链表做pta7-2 重排链表

### PTA 7-2 重排链表解法

对于PTA平台上的7-2重排链表题目，可以采用类似于LeetCode第143题的方法来解决这个问题。具体来说，在处理单链表 \(L\) 的时候，目标是将其重新排列成特定模式：\(L_0 \rightarrow L_n \rightarrow L_1 \rightarrow L_{n-1} \rightarrow L_2 \rightarrow L_{n-2}\ldots\)[^3]。

为了实现这一目标，通常会采取以下策略：

#### 方法概述

1. **找到中间节点**
首先利用快慢指针技术定位到链表的中间位置。这一步骤有助于后续操作中的效率提升。

2. **反转后半部分链表**
找到中间节点之后，将链表从中点断开并单独对后面的部分执行翻转操作。这样做可以让后面的元素按照相反顺序连接起来。

3. **交替合并两段链表**
接下来就是把前一半未改变顺序的链表同已经反转过的另一半依次交错相连，从而形成最终所需的输出形式。

下面是具体的Python代码实现方式：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reorderList(head: ListNode) -> None:
    if not head or not head.next:
        return
    
    # Step 1: Find the middle of the list using slow and fast pointers.
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
    # Step 2: Reverse the second half of the linked list starting from 'slow'.
    prev, curr = None, slow
    while curr:
        temp_next = curr.next
        curr.next = prev
        prev = curr
        curr = temp_next
        
    # Now `prev` points to the last element (new start point after reversing).
    
    # Step 3: Merge two halves by alternating nodes between them.
    first_half, second_half = head, prev
    while second_half.next:
        tmp_first = first_half.next
        tmp_second = second_half.next
        first_half.next = second_half
        second_half.next = tmp_first
        first_half = tmp_first
        second_half = tmp_second

此算法的时间复杂度主要取决于遍历次数以及每次遍历时的操作量级，整体时间复杂度大约为O(n)，其中n代表链表长度；空间复杂度则保持在常数级别O(1)，因为只用了有限数量额外变量存储临时状态信息。

pta 6-2 两个有序链表序列的合并

这道题可以采用归并排序的思想，把两个有序链表合并成一个有序链表。

具体实现步骤如下：

1. 定义一个新链表，用来存储合并后的结果。

2. 定义指针p和q分别指向两个有序链表的头结点，比较p和q指向的节点的大小，将较小的节点插入新链表中。

3. 如果p或q其中一个链表已经遍历完了，那么把另一个链表剩余的部分直接插入到新链表中。

4. 重复步骤2和步骤3，直到两个链表都遍历完毕。

5. 返回新链表的头结点。

C++代码如下：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode *dummy = new ListNode(0);
    ListNode *cur = dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    cur->next = (l1 ? l1 : l2);
    return dummy->next;
}