单链表的反转java实现_单链表反转java

题目：
给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。

单链表的基本结构

public class ListNode {
    // 值
    int val;
    // 指向下一个节点的指针
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
1
2
3
4
5
6
7
8
9
10

链表反转实现：

// 传入链表的头节点
// 返回反转后链表的头节点
public ListNode ReverseList(ListNode head) {
        // 如果头节点为空或者头节点下一个节点为空，直接返回头节点
        if(head==null||head.next==null){
            return head;
        }
        // 反转的是当前节点，所以需要知道前一个节点是什么，以便当前节点指
        // 向前一个节点(pre节点)，由于反转后需要跳往下一个节点，继续下一
        // 个节点的反转操作，所以需要记录当前节点下一个节点信息即
        // (next节点)。
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        // 当前节点不为空，进行当前节点的反转处理
        while(cur!=null){
            //记录当前节点的next节点
            next = cur.next;
            // 当前节点反转(当前节点next指向前一个节点)
            cur.next = pre;
            // 平移处理下一个节点
            // 前一个节点前移指定当前节点
            pre = cur;
            // 当前节点前移指向下一个节点，继续处理下一个节点反转
            cur = next;
        }
        return pre;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28