03-链表

链表

数组转链表

递归方式

JavaScript版

class Node {
  constructor (value, next) {
    this.value = value;
    this.next = next;
  }
}
var arrayToLinkedList = function (arr, left = 0) {
  let head = null;
  if (left < arr.length) {
    head = new Node(arr[left], null);
    head.next = arrayToLinkedList(arr, left + 1);
  }
  return head;
}
var sortArray = function (nums) {
  let linkedList = arrayToLinkedList(nums);
  let curr = linkedList;
  let i = 0;
  while (curr != null) {
    nums[i] = curr.value;
    curr = curr.next;
    i++;
  }
  return nums;
};

Java版

class Solution {
  private class Node {
    int value;
    Node next;
    public Node (int value, Node next) {
      this.value = value;
      this.next = next;
    }
  }
  public Node arrayToLinkedList (int[] arr) {
    return arrayToLinkedList(arr, 0);
  }
  private Node arrayToLinkedList (int[] arr, int left) {
    Node head = null;
    if (left < arr.length) {
      head = new Node(arr[left], null);
      head.next = arrayToLinkedList(arr, left + 1);
    }
    return head;
  }
  public int[] sortArray(int[] nums) {
    Node LinkedList = arrayToLinkedList(nums);
    Node curr = LinkedList;
    int i = 0;
    while (curr != null) {
      nums[i] = curr.value;
      curr = curr.next;
      i++;
    }
    return nums;
  }
}

非递归方式

JavaScript版

class Node {
  constructor (value, next) {
    this.value = value;
    this.next = next;
  }
}
var arrayToLinkedList = function (arr) {
  if (arr.length == 0) {
    return null;
  }
  let head = new Node(arr[0], null);
  let curr = head;
  for (let i = 1; i < arr.length; i++) {
    curr.next = new Node(arr[i], null);
    curr = curr.next;
  }
  return head;
}
var sortArray = function (nums) {
  let linkedList = arrayToLinkedList(nums);
  let curr = linkedList;
  let i = 0;
  while (curr != null) {
    nums[i] = curr.value;
    curr = curr.next;
    i++;
  }
  return nums;
};

Java版

class Solution {
  private class Node {
    int value;
    Node next;
    public Node (int value, Node next) {
      this.value = value;
      this.next = next;
    }
  }
  public Node arrayToLinkedList (int[] arr) {
    if (arr.length == 0) {
      return null;
    }
    Node head = new Node(arr[0], null);
    Node curr = head;
    for (int i = 1; i < arr.length; i++) {
      curr.next = new Node(arr[i], null);
      curr = curr.next;
    }
    return head;
  }
  public int[] sortArray(int[] nums) {
    Node LinkedList = arrayToLinkedList(nums);
    Node curr = LinkedList;
    int i = 0;
    while (curr != null) {
      nums[i] = curr.value;
      curr = curr.next;
      i++;
    }
    return nums;
  }
}

链表翻转

递归方式

JavaScript版

var reverseList = function(head) {
	if (head == null || head.next == null) {
    return head;
  }
  let newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
};

Java版

class Solution {
    public ListNode reverseList(ListNode head) {
      if (head == null || head.next == null) {
        return head;
      }
      ListNode newHead = reverseList(head.next);
      head.next.next = head;
      head.next = null;
      return newHead;
    }
}

非递归方式

JavaScript版

var reverseList = function(head) {
  let prev = null;
  let curr = head;
  while (curr != null) {
    let next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
};

Java版

class Solution {
    public ListNode reverseList(ListNode head) {
      ListNode prev = null;
      ListNode curr = head;
      while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
      }
      return prev;
    }
}