单链表是一种常见的数据结构,由一个个节点通过指针方式连接而成,每个节点由两部分组成:一是数据域,用于存储节点数据。二是指针域,用于存储下一个节点的地址。leetcode中的单链表节点在Java中定义如下:
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
说下思路:所谓的单链表反转,就是把每个节点的指针域由原来的指向下一个节点变为指向其前一个节点。但由于单链表没有指向前一个节点的指针域,因此我们需要增加一个指向前一个节点的指针pre,用于存储每一个节点的前一个节点。此外,还需要定义一个保存当前节点的指针cur,以及下一个节点的next。定义好这三个指针后,遍历单链表,将当前节点的指针域指向前一个节点,之后将定义三个指针往后移动,直至遍历到最后一个节点停止。
ListNode cur = head.next;
ListNode pre = null;
while(cur != null){ //注意这里条件是cur != null
ListNode nextNode = cur.next;
cur.next = pre;
pre = cur;
cur = nextNode;
}
写成函数形式:
public ListNode reverseList(ListNode head)
{
ListNode cur = head.next;
ListNode pre = null;
while(cur != null){
ListNode nextNode = cur.next;
cur.next = pre;
pre = cur;
cur = nextNode;
}
return pre;
}
这个操作非常重要!!!