Java带头节点的单链表逆置

在Java中，带头节点的单链表逆置通常通过迭代或递归的方式实现。这里是一个简单的迭代方法：

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    while (current != null) {
        // 保存当前节点的下一个节点
        ListNode nextTemp = current.next;
        
        // 将当前节点的next指向前一个节点
        current.next = prev;
        
        // 移动prev和current到下一位
        prev = current;
        current = nextTemp;
    }
    
    // 返回新的头节点，即原链表的尾节点
    return prev;
}

这个算法的工作原理是每次循环都将当前节点的`next`指向`prev`，然后将`prev`和`current`向后移动一位，直到遍历完整个链表。最后返回`prev`作为新的头节点。

相关问题

带头结点单链表就地逆置

很高兴为您解答关于带头结点单链表就地逆置的问题。带头结点单链表的就地逆置可以通过从首节点开始反转每一个节点的指向，直到链表末尾完成。这里给出一个简单实现的C++代码：

#include<iostream>
using namespace std;

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

ListNode* reverseList(ListNode* head){
    if(head==NULL || head->next==NULL) return head;
    ListNode* pre = head;
    ListNode* cur = head->next;
    ListNode* nxt;
    pre->next = NULL;
    while(cur!=NULL){
        nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}

int main(){
    int n;
    cin>>n;
    ListNode* head = new ListNode(0);
    ListNode* p = head;
    for(int i=0;i<n;i++){
        int x; cin>>x;
        ListNode* node = new ListNode(x);
        p->next = node;
        p = p->next;
    }
    head = reverseList(head);
    p = head->next;
    while(p!=NULL){
        cout<<p->val<<" ";
        p = p->next;
    }
    cout<<endl;
    return 0;
}

该程序首先定义了一个ListNode类作为单链表的节点，然后定义了一个reverseList函数对带头结点的链表进行就地逆置。在main函数中，程序首先读入链表的长度n以及每个节点的值，然后通过一个循环将链表构建完成。接下来，我们对链表进行就地逆置，最后按照逆序输出每个节点的值。希望我的回答能够帮助到您，如有疑问，请随时追问。

有头结点单链表逆置c语言

以下是用C语言实现有头结点单链表逆置的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 定义链表结构体
typedef struct node {
    int data;
    struct node* next;
} Node;

// 创建链表
Node* createList(int n) {
    Node* head = (Node*)malloc(sizeof(Node));  // 创建头结点
    head->next = NULL;
    Node* cur = head;
    for (int i = 1; i <= n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = i;
        newNode->next = NULL;
        cur->next = newNode;
        cur = newNode;
    }
    return head;
}

// 遍历链表
void traverseList(Node* head) {
    Node* cur = head->next;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// 链表逆置
void reverseList(Node* head) {
    Node* pre = head->next;
    Node* cur = pre->next;
    pre->next = NULL;
    while (cur != NULL) {
        Node* next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    head->next = pre;
}

int main() {
    Node* head = createList(5);
    printf("原链表：");
    traverseList(head);
    reverseList(head);
    printf("逆置后的链表：");
    traverseList(head);
    return 0;
}

该代码中，首先定义了链表结构体 `Node`，包含数据域和指向下一个节点的指针。`createList` 函数用于创建有头结点的单链表，返回头结点指针。`traverseList` 函数用于遍历链表并打印每个节点的数据。`reverseList` 函数用于逆置链表。在 `main` 函数中，先创建一个有 5 个节点的链表并打印，然后调用 `reverseList` 函数逆置链表并再次打印。