题目：输入一个链表，反转链表后，输出新链表的表头。 思想： 1. 题目中所给的是单链表，想一想 反转后的样子：最后一个结点指向倒数第二个，倒数第二个指向倒数第三个，…第一个指向Null 2.知道了反转后各个结点指向哪之后，就需要开始调整每个结点的next 指针 3.这就需要把结点挨个从链表上摘下来，做调整； 4.需要两个指针 pre 记录其前一个结点的位置，好让该节点的next指针指向前一个结点，但是在指向前一个结点前 需要用一个指针P记录后一个结点的位置， 注意 null；
/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode ReverseList(ListNode head) { //初始化pre指针，用于记录当前结点的前一个结点地址 ListNode pre = null; //初始化p指针，用于记录当前结点的下一个结点地址 ListNode p = null; //head指向null时，循环终止。 while(head != null){ //先用p指针记录当前结点的下一个结点地址。 p = head.next; //让被当前结点与链表断开并指向前一个结点pre。 head.next = pre; //pre指针指向当前结点 结点后移 pre = head; //head指向p(保存着原链表中head的下一个结点地址) head = p; } return pre;//当循环结束时,pre所指的就是反转链表的头结点 } }C语言实现
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pHead ListNode类 * @return ListNode类 */ struct ListNode* ReverseList(struct ListNode* pHead ) { //定义三个指针 分别是 头结点 头结点之前 头结点之后 struct ListNode *pre =NULL; struct ListNode *p1=pHead; struct ListNode *p2=NULL; while(p1!=NULL){ p2=p1->next;//指定p2在p1的下一个结点 p1->next=pre;//将p1与链表断开 指向pre; pre=p1;//pre 指向原来p1的位置 p1=p2;// p1后移至 p2的 位置 } return pre; }