第十五题 反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

方法一

一、分析

• 题目所给的是单链表，想了一下反转后的样子：最后一个结点指向倒数第二个，倒数第二个指向倒数第三个，……，第二个指向第一个，第一个指向null;
• 知道了反转后各个结点指向哪之后，就需要开始调整每个结点的next指针。
• 这就需要把结点挨个从链表上摘下来，做调整；(该方法的精髓所在)
• 这个调整过程需要两个指针辅助：pre记录其前一个结点位置，好让该结点的next指针指向前一个结点，但是在指向前一个结点前需要用一个指针p记录后一个结点地址，避免结点丢失。
• 例子：
  • 以head结点为例步骤如下：
  • 1.反转后head是指向null，所以未反转的时候其前一个结点应该是null，初始化pre指针为null；
  • 2.用p指针记录head的下一个结点head.next；
  • 3.从链表上摘下head，即让head.next指向pre；
  • 4.此时已完成head结点的摘取及与前一个节点的连接，则我们需要操作下一个结点：故需移动pre和head，让pre指向head，head指向下一个节点。
  • 重复这四个操作直到head走完原链表，指向null时，循环结束，返回pre。

    二、代码

    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所指的就是反转链表的头结点
    }

    方法二

    一、分析

    牛客提交不成功但是本地运行是可以的,实现的是将单链表转换为双链表,方法是找到最后一个节点然后在该节点后面不断的添加(添加项的确认是通过对原始的head不同的遍历次数来依次从倒数第二向前取得).(太麻烦)

    二、代码

public static ListNode ReverseList(ListNode head) {
        ListNode iter = head;//用来遍历链表中的个数
        ListNode curr = null;
        ListNode tail = null;//最后一个节点
        ListNode mid = null;
        ListNode temp = null;//用来临时存放从后向前取得的节点
        int count = 1;
        int k = 0;
        while(iter.next!=null)
        {
            iter = iter.next;
            tail = iter;
            count++;
        }
        mid = tail;
        for(int i = 1;i<count;i++)
        {
            curr = head;
            k=count-i-1;
            if(k==0)
            {
                temp = head;
            }
            while(k>0)
            {
                curr = curr.next;
                temp = curr;
                k--;
            }
            mid.next = temp;
            mid = mid.next;
        }
        return tail;
    }