206.翻转链表

2023-12-26 12:08:47
//Definition for singly-linked list.
public class ListNode {
	int val;
	ListNode next;
	ListNode() {}
	ListNode(int val) { this.val = val; }
	ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

方法一:从前往后把所有指针反向

class Solution {
     public ListNode reverseList(ListNode head) {
     	// 把所有的指针反向
    	ListNode pre = null;
     	ListNode cur = head;
     	ListNode temp = null;// 保存cur的下一个节点
     	while (cur != null) {
     	temp = cur.next;
     	cur.next = pre;
     	pre = cur;
     	cur = temp;
     	}
     	return pre;
     }
}

方案二:递归 从前往后把所有指针反向

class Solution {
	ListNode reverse(ListNode pre, ListNode cur) {
		if (cur == null) {
     		return pre;
	    }
		ListNode temp = cur.next;
     	cur.next = pre;
     	return reverse(cur, temp);
	}

	public ListNode reverseList(ListNode head) {
    	// 把所有的指针反向
    	return reverse(null,head);
	}
}

方案三:递归 从后往前把所有指针反向

class Solution {
	public ListNode reverseList(ListNode head) {
		if (head == null)//链表本身为空
            return null;
        if (head.next == null)//为了找到翻转之后的头节点
            return head;
        ListNode last = reverseList(head.next);
        // 反转指针
        head.next.next = head;
        head.next = null;//对中间节点无效 为了链表的原始头节点准备的
        return last;
    }
}

官方解更好的地方

直接看官方解做的

做题卡住的点

每次循环或者迭代只翻转一个指针
要把反转之后的头节点找到

文章来源:https://blog.csdn.net/qq_44047415/article/details/135215191
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。