206. 反转链表

1、题目介绍

反转一个单链表。

试题链接：https://leetcode-cn.com/problems/reverse-linked-list/

2、双指针做法

2.1、java

    public static ListNode reverseList(ListNode head) {
        if(head == null) return null;
        //构造头指针
        ListNode index = new ListNode(-1);
        index.next = head;

        ListNode pCurrent = head;
        while (pCurrent.next != null) {
            //使辅助移动到最后
            pCurrent = pCurrent.next;
        }

        while (index.next != pCurrent) {
            ListNode temp = index.next;
            index.next = temp.next;
            temp.next = pCurrent.next;
            pCurrent.next = temp;
        }

        return index.next;
    }

输出结果：

2.2、C

struct ListNode* reverseList(struct ListNode* head){
        if(head == NULL) return NULL;
        //构造头指针
        struct ListNode* index = (struct ListNode*)malloc(sizeof(struct ListNode));
        index->val = -1;
        index->next = head;

        struct ListNode* pCurrent = head;
        while (pCurrent->next != NULL) {
            //使辅助移动到最后
            pCurrent = pCurrent->next;
        }

        while (index->next != pCurrent) {
            struct ListNode* temp = index->next;
            index->next = temp->next;
            temp->next = pCurrent->next;
            pCurrent->next = temp;
        }

        return index->next;
}

输出结果：

3、递归做法

3.1、java

    public static ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;

//        0、1->2->3->4->5->null
//        1、2->3->4->5->null
//        2、3->4->5->null
//        3、4->5->null
//        4、5->null
//        5
        ListNode newNode = reverseList(head.next);

//        System.out.println(head);

        head.next.next = head;
        head.next = null;

        return newNode;
    }

输出结果：

3.2、C

struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL || head->next == NULL) return head;

    struct ListNode* newNode = reverseList(head->next);

    head->next->next = head;
    head->next = NULL;

    return newNode;
}

输出结果：

206. 反转链表

原文：https://www.cnblogs.com/xgp123/p/12394534.html