反转链表

反转链表

//ide版本
void main() {
    //给你单链表的头节点head ，请你反转链表，并返回反转后的链表。
    ListNode head = new ListNode(1);
    head.next = new ListNode(2);
    head.next.next = new ListNode(3);
    head.next.next.next = new ListNode(4);
    head.next.next.next.next = new ListNode(5);
    printList(head);
    ListNode reversedHead = reverseList(head);
    printList(reversedHead);
}

public ListNode reverseList(ListNode head) {
    if(head == null){
        return head;
    }
    //创建一个值为0的新节点dummy,下一个节点指向head
    ListNode dummy = new ListNode(0,head);
    ListNode pre = dummy;
    //当前节点
    ListNode cur = pre.next;
    while(cur.next != null){
        //下一个节点
        ListNode next = cur.next;
        //当前的下一个执行next的后一个，next需要到前面
        cur.next = next.next;
        //下一个节点的下一个指向pre的下一个
        next.next = pre.next;
        //pre的下一个是next
        pre.next = next;
    }
    return dummy.next;
}

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

class ListNode{
    int val ;
    ListNode next;
    ListNode(){};
    ListNode(int val){
        this.val = val;
    }
    ListNode(int val,ListNode next){
        this.val = val;
        this.next = next;
    }
}