Description

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:

Input: head = [1,2]
Output: [2,1]
Example 3:

Input: head = []
Output: []

Constraints:

The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Answer and Explaining

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *pre=NULL;
    struct ListNode *next=NULL;

    if(head==NULL) return NULL;
    while(head!=NULL)
    {
        next = head ->next;//儲存節點到next
        head->next=pre;//將下個節點反轉到前個節點
        pre=head;//移動pre到目前位置
        head=next;//移動head到下個位置
    }
    return pre;
}

Testing

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

// Definition for singly-linked list.
struct ListNode { //定義ListNode structure
    int val;
    struct ListNode *next;
};

// Function to reverse the linked list.

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *pre = NULL;
    struct ListNode *next = NULL;

    while (head != NULL) {
        next = head->next;
        head->next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

// Helper function to create a new ListNode.
//設置新增節點(輔助測試程式)
struct ListNode* createNode(int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// Helper function to print the linked list.
// 印出LinkedLsit
void printList(struct ListNode* head) {
    struct ListNode* current = head;
    while (current != NULL) {
        printf("%d -> ", current->val); //不斷印出下個value
        current = current->next;
    }
    printf("NULL\n");
}

// Test function for reverseList.
void testReverseList() {
    // Creating the linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
    struct ListNode* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    printf("Original list: \n");
    printList(head);

    // Reversing the linked list
    struct ListNode* reversedHead = reverseList(head);

    printf("Reversed list: \n");
    printList(reversedHead);//印出結果
}

int main() {
    testReverseList();
    return 0;
}