题解 |迭代的两种写法 #反转链表#

迭代的写法也叫双指针的写法

写法一：不带头结点的头插法，将目标链表的尾节点后的结点作为新节点插入目标链表的第1个位置，即目标链表的首结点之前。

自己根据王道课程的单链表建立的那节视频提到的带头结点的头插法，想的不带头结点的头插法。

/*
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 ){//处理空链表
            return null;
        }
        ListNode last = head;//使用last指针指（尾指针）向目标链表的头尾结点
        ListNode fist = last;//使用fist（首指针）指针指向目标链表的头首结点
        while(last.next != null){//当尾指针后面没有节点时，表示链表只有1个节点无需反转|链表反转完成
            ListNode newNode = last.next;//当尾指针后面有节点时，取尾指针后的节点
            last.next = newNode.next;
            newNode.next = fist;//将取出的节点插入链表的第1个位置，即fist前
            fist = newNode;//首指针指向新插入的节点
        }
        return fist;

    }
}

写法二：将当前节点的next反转指向前一个节点

实际上是将一个链表分成了两个链表。

• pre为新链表的首结点，表示目标链表，初始为null。
• curr为待处理链表的首结点，表示待处理链表。
• 取curr链表的首结点，插入prev链表的第1个位置，重复此操作，直到curr链表为空时结束。

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null,curr=head,next;
        while(curr != null){
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}