一【题目类别】

链表

二【题目难度】

简单

三【题目编号】

206.反转链表

四【题目描述】

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

五【题目示例】

示例 1： 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] 示例 2： 输入：head = [1,2] 输出：[2,1] 示例 3： 输入：head = [] 输出：[]

六【题目提示】

链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000

七【题目进阶】

链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

八【解题思路】

这种类型的题目很简单，在考研的题目中也算基础题。我们只需要先把头结点断开，然后从左到右遍历整个链表，记录后面的结点，一一将其连接到前一个结点即可。注意最后返回是被连接的结点而不是遍历的结点，还需要注意的是空返回

九【时间频度】

时间复杂度： O ( n ) O(n) O(n)，其中 n n n为链表长度

十【代码实现】

1. Java语言版

package LinkedList;

public class p206_ReverseLinkedList {
          
   

    int val;
    p206_ReverseLinkedList next;

    public p206_ReverseLinkedList() {
          
   
    }

    public p206_ReverseLinkedList(int val) {
          
   
        this.val = val;
    }

    public p206_ReverseLinkedList(int val, p206_ReverseLinkedList next) {
          
   
        this.val = val;
        this.next = next;
    }

    public static void main(String[] args) {
          
   
        p206_ReverseLinkedList node1 = new p206_ReverseLinkedList(1);
        p206_ReverseLinkedList node2 = new p206_ReverseLinkedList(2);
        p206_ReverseLinkedList node3 = new p206_ReverseLinkedList(3);
        p206_ReverseLinkedList node4 = new p206_ReverseLinkedList(4);
        p206_ReverseLinkedList node5 = new p206_ReverseLinkedList(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        p206_ReverseLinkedList res = reverseList(node1);
        while (res != null) {
          
   
            if (res.next != null) {
          
   
                System.out.print(res.val + "->");
            } else {
          
   
                System.out.print(res.val);
            }
            res = res.next;
        }
    }

    public static p206_ReverseLinkedList reverseList(p206_ReverseLinkedList head) {
          
   
        if (head == null) {
          
   
            return head;
        }
        p206_ReverseLinkedList p = head;
        p206_ReverseLinkedList q = head.next;
        p206_ReverseLinkedList temp;
        p.next = null;
        while (q != null) {
          
   
            temp = q.next;
            q.next = p;
            p = q;
            q = temp;
        }
        return p;
    }

}

2. C语言版

#include<stdio.h>

struct ListNode
{
          
   
	int val;
	struct ListNode *next;
};

struct ListNode* reverseList(struct ListNode* head)
{
          
   
	if (head == NULL)
	{
          
   
		return head;
	}
	struct ListNode* p = head;
	struct ListNode* q = head->next;
	struct ListNode* temp;
	p->next = NULL;
	while (q != NULL)
	{
          
   
		temp = q->next;
		q->next = p;
		p = q;
		q = temp;
	}
	return p;
}

/*主函数省略*/

十一【提交结果】

1. Java语言版
2. C语言版