文章目录

206.反转链表1.题目描述2.题目示例3.思路及代码

206.反转链表

1.题目描述

反转一个单链表。

2.题目示例

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶：你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

3.思路及代码

思路一：迭代，三指针法代码： /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { //边界条件 if(head == null || head.next == null){ return head; } //三指针法 ListNode first = head; ListNode second = first.next; ListNode third = second.next; //进行反转 while(third != null){ second.next = first; first = second; second = third; third = third.next; } //更改指向 second.next = first; head.next = null; head = second; //返回新的头节点 return head; } }

运行结果

思路二：递归

class Solution { public ListNode reverseList(ListNode head) { if(head==null || head.next==null) return head; ListNode p = reverseList(head.next); head.next.next = head; head.next = null; return p; } } 运行结果 思路三：头插法代码： /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode ReverseList(ListNode head) { if(head == null || head.next == null){ return head; } ListNode new_head = null; while(head != null){ ListNode p = head; head = head.next; p.next = new_head; new_head = p; } return new_head; } } 运行结果