单链表adt模板简单应用算法设计：单链表中前 m 个元素和后 n 个元素的互换

算法设计：

1. 判断链表是否为空，若为空则直接返回。

2. 判断链表长度是否小于 m+n，若小于则直接返回。

3. 定义三个指针：p1、p2、p3，分别指向第 m-1 个元素、第 m 个元素、第 m+n 个元素的前一个元素。

4. 将 p2 指向的元素插入到 p3 指向的元素的后面。

5. 将 p1 指向的元素插入到 p2 指向的元素的后面。

6. 将 p3 指向的元素插入到 p1 指向的元素的后面。

7. 返回链表头节点。

代码实现：

def swap_m_n(head, m, n):
    if not head:
        return head
    length = 0
    p = head
    while p:
        length += 1
        p = p.next
    if length < m + n:
        return head
    p1 = head
    for i in range(m-2):
        p1 = p1.next
    p2 = p1.next
    p3 = p2
    for i in range(n):
        p3 = p3.next
    p1.next = p3
    p2.next = p3.next
    p3.next = p2
    return head

其中，head 为链表头节点，m 和 n 分别为前 m 个元素和后 n 个元素。

相关问题

顺序表adt模板设计及简单应用：将顺序表中前 m 个元素和后 n 个元素进行互换

顺序表ADT模板设计：

1. 定义顺序表结构体，包含元素数组和当前元素个数等信息。

2. 初始化顺序表，分配元素数组空间，将当前元素个数置为。

3. 插入元素，判断是否已满，若未满则在末尾插入元素并更新当前元素个数。

4. 删除元素，判断是否为空，若非空则删除指定位置的元素并更新当前元素个数。

5. 获取元素，判断是否越界，若未越界则返回指定位置的元素。

6. 修改元素，判断是否越界，若未越界则修改指定位置的元素。

7. 互换元素，将顺序表中前m个元素和后n个元素进行互换，需要先判断m和n是否合法，然后使用一个临时数组进行交换。

简单应用：

假设有一个顺序表L，其中有10个元素，需要将前3个元素和后4个元素进行互换，可以按照以下步骤实现：

1. 判断m和n是否合法，即m+n是否等于L中元素个数。

2. 创建一个临时数组temp，将前m个元素复制到temp中。

3. 将后n个元素依次移动到前m个元素的位置上。

4. 将temp中的元素依次移动到后n个元素的位置上。

5. 更新顺序表L的当前元素个数。

代码示例：

#define MAXSIZE 100 // 定义顺序表最大长度

typedef struct {
    int data[MAXSIZE]; // 元素数组
    int length; // 当前元素个数
} SqList;

// 初始化顺序表
void InitList(SqList *L) {
    L->length = ;
}

// 插入元素
void Insert(SqList *L, int pos, int x) {
    if (L->length == MAXSIZE) {
        printf("List is full.\n");
        return;
    }
    if (pos < 1 || pos > L->length + 1) {
        printf("Invalid position.\n");
        return;
    }
    for (int i = L->length; i >= pos; i--) {
        L->data[i] = L->data[i - 1];
    }
    L->data[pos - 1] = x;
    L->length++;
}

// 删除元素
void Delete(SqList *L, int pos) {
    if (L->length == ) {
        printf("List is empty.\n");
        return;
    }
    if (pos < 1 || pos > L->length) {
        printf("Invalid position.\n");
        return;
    }
    for (int i = pos; i < L->length; i++) {
        L->data[i - 1] = L->data[i];
    }
    L->length--;
}

// 获取元素
int GetElem(SqList *L, int pos) {
    if (pos < 1 || pos > L->length) {
        printf("Invalid position.\n");
        return -1;
    }
    return L->data[pos - 1];
}

// 修改元素
void SetElem(SqList *L, int pos, int x) {
    if (pos < 1 || pos > L->length) {
        printf("Invalid position.\n");
        return;
    }
    L->data[pos - 1] = x;
}

// 互换元素
void Swap(SqList *L, int m, int n) {
    if (m + n != L->length) {
        printf("Invalid parameters.\n");
        return;
    }
    int temp[m];
    for (int i = ; i < m; i++) {
        temp[i] = L->data[i];
    }
    for (int i = ; i < n; i++) {
        L->data[i] = L->data[m + i];
    }
    for (int i = ; i < m; i++) {
        L->data[n + i] = temp[i];
    }
    L->length = m + n;
}

单链表ADT模板应用算法设计:长整数加法运算(不使用单链表存储计算结果)

算法设计：

1. 定义单链表的结构体，包含一个整数和一个指向下一个节点的指针。
2. 分别读入两个长整数并将它们存储在两个单链表中。
3. 从两个单链表的头节点开始，依次将每个节点的整数相加，并将结果存储在一个新的单链表中。
4. 对于每个节点的整数相加，需要考虑进位的情况，即若相加结果大于9，则需要向高位进位。
5. 最后得到的单链表即为两个长整数的和，将其输出即可。

伪代码：

定义单链表结构体：
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

读入两个长整数并将它们存储在两个单链表中：
ListNode* l1 = new ListNode(0);
ListNode* l2 = new ListNode(0);
ListNode* p1 = l1;
ListNode* p2 = l2;
while (x != 0) {
    int digit = x % 10;
    p1->next = new ListNode(digit);
    p1 = p1->next;
    x /= 10;
}
while (y != 0) {
    int digit = y % 10;
    p2->next = new ListNode(digit);
    p2 = p2->next;
    y /= 10;
}

从两个单链表的头节点开始，依次将每个节点的整数相加，并将结果存储在一个新的单链表中：
ListNode* ans = new ListNode(0);
ListNode* p3 = ans;
p1 = l1->next;
p2 = l2->next;
int carry = 0;
while (p1 != NULL || p2 != NULL) {
    int x = (p1 != NULL) ? p1->val : 0;
    int y = (p2 != NULL) ? p2->val : 0;
    int sum = x + y + carry;
    carry = sum / 10;
    p3->next = new ListNode(sum % 10);
    p3 = p3->next;
    if (p1 != NULL) p1 = p1->next;
    if (p2 != NULL) p2 = p2->next;
}
if (carry > 0) {
    p3->next = new ListNode(carry);
}

输出结果：
p3 = ans->next;
while (p3 != NULL) {
    cout << p3->val;
    p3 = p3->next;
}

注意事项：

1. 在定义单链表结构体时，要考虑到链表的头节点，即第一个节点不存储有效数据。
2. 在节点的整数相加时，需要考虑到两个单链表长度不一致的情况。