Leetcode-206-反转链表

Leecode-206-Reverse Linked List

思路：双指针/递归

题目描述

将一个链表进行翻转，如下例：

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Solution：双指针

• 申请两个指针，第一个指针叫 pre，最初是指向 null 的。

• 第二个指针 cur 指向 head，然后不断遍历 cur。

• 每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。

• 当都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。

下面再看另外一种解法：

Solution：递归

• 终止的条件是当前节点或者下一个节点==null
• 在函数内部，改变节点的只想，有head.next.next = head , 其实也就是head的下一个节点的next指向自己（这里原因看图一下便知）
• 递归函数中cur其实就是链表每次循环的最后一个节点。

Java

Solution :双指针

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode tmp = null;
        ListNode cur = head;

        // 实现局部翻转
        while(cur != null){
            // tmp 记录下当前cur.next指向
            tmp = cur.next;
            // 断开链接
            cur.next = pre;

            // cur和pre都向后移动一位
            pre = cur;
            cur = tmp;
        }
        // 这是pre刚好是最后一个节点，cur已经到了null
        return pre;
    }
}

• 时间复杂度：遍历一遍链表，所以是O(n)
• 空间复杂度：没有额外的辅助内存->O(1)

测试用例：

public static void main(String[] args) {
    // l1
    ListNode li11 = new ListNode(1);
    ListNode li12 = new ListNode(2);
    ListNode li13 = new ListNode(3);
    ListNode li14 = new ListNode(6);
    li11.next = li12;
    li12.next = li13;
    li13.next = li14;
    li14.next = null;

    Solution solution = new Solution();
    printList(solution.reverseList(li11));
}

public static void printList(ListNode head) {
    ListNode curNode = head;
    while(curNode != null) {
        System.out.print(curNode.val + "->");
        curNode = curNode.next;
    }
    System.out.print("NULL");
}

Solution :递归

class Solution {
	public ListNode reverseList(ListNode head) {
		//递归终止条件是当前为空，或者下一个节点为空
		if(head==null || head.next==null) {
			return head;
		}
		//这里的cur就是最后一个节点
		ListNode cur = reverseList(head.next);
		//这里请配合动画演示理解
		//如果链表是 1->2->3->4->5，那么此时的cur就是5
		//而head是4，head的下一个是5，下下一个是空
		//所以head.next.next 就是5->4
		head.next.next = head;
		//防止链表循环，需要将head.next设置为空
		head.next = null;
		//每层递归函数都返回cur，也就是最后一个节点
		return cur;
	}
}

• 时间复杂度：遍历一遍链表，所以是O(n)

• 空间复杂度：没有额外的辅助内存->O(1)

Python

Solution :

打赏