LeetCoding--Reverse Linked List（Java）

浏览数：29 / 时间：2015年06月08日

翻转单链表（要注意的是是否含有头结点）：

思路一：每次将第一个节点后的那个节点放到第一个位置。若无头结点，则额外需要一个指针记录首节点。

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null)
              return null;
        if(head.next == null)
              return head;
        ListNode h = head;
        while(head.next!=null){
            ListNode p = head.next;
            head.next = p.next;
            p.next = h;
            h = p;
        }
        return h;
    }
}

思路二：额外创建新的空间，用一个指针遍历原来链表，每次将新建的节点插入到新链表的开始位置，代码：

      public static ListNode reverseList1(ListNode head) {
            //每次都是将第一个节点后面的节点放到头结点后面
          if(head == null)
              return null;
          if(head.next==null)
              return head;
          
          ListNode h = new ListNode(head.val);
          
          while(head.next!=null){
              ListNode t = new ListNode(head.val);
              t.next = h;
              head = head.next;
          }
          return h;
        }

若有头结点：

思路一：

      public static ListNode reverseList(ListNode head) {
            //每次都是将第一个节点后面的节点放到头结点后面
          if(head == null)
              return null;
          ListNode p = head.next;
          while(p.next!=null){
              ListNode q = p.next;
              p.next = q.next;
              q.next = head.next;
              head.next = q;
          }
            return head;
        }

思路二：

      public static ListNode reverseList1(ListNode head) {
            //每次都是将第一个节点后面的节点放到头结点后面
          if(head == null)
              return null;
          if(head.next==null)
              return head;
          
          ListNode h = new ListNode(-1);
          h.next=null;
          ListNode p = head.next;
          while(p!=null){
              ListNode t = new ListNode(p.val);
              t.next = h.next;
              h.next = t;
              p = p.next;
          }
          return h;
        }