1. 链表

数组是一种顺序表，index与value之间是一种顺序映射，以O(1)的复杂度访问数据元素。但是，若要在表的中间部分插入（或删除）某一个元素时，需要将后续的数据元素进行移动，复杂度大概为O(n)。链表（Linked List）是一种链式表，克服了上述的缺点，插入和删除操作均不会引起元素的移动；数据结构定义如下：

public class ListNode {

  String val;

  ListNode next;

  // ...

}

常见的链表有单向链表（也称之为chain），只有next指针指向后继结点，而没有previous指针指向前驱结点。

链表的插入与删除操作只涉及到next指针的更新，而不会移动数据元素。比如，要在FAT与HAT插入结点GAT，如图所示：

Java实现：

ListNode fat, gat;

gat.next = fat.next;

fat.next = gat;

又比如，要删除结点GAT，如图所示：

Java实现：

fat.next = fat.next.next;

从上述代码中，可以看出：因为没有前驱指针，一般在做插入和删除操作时，我们需要通过操作前驱结点的next指针开始。

2. 题解

237. Delete Node in a Linked List
删除指定结点。由于是单向链表，因此只需更新待删除节点即可。

public void deleteNode(ListNode node) {

  node.val = node.next.val;

  node.next = node.next.next;

}

203. Remove Linked List Elements
删除指定值的结点。用两个指针实现，curr用于遍历，prev用于暂存前驱结点。

public ListNode removeElements(ListNode head, int val) {

  ListNode fakeHead = new ListNode(Integer.MIN_VALUE);

  fakeHead.next = head;

  for (ListNode curr = head, prev = fakeHead; curr != null; curr = curr.next) {

    if (curr.val == val) { // remove

      prev.next = curr.next;

    } else { // traverse

      prev = prev.next;

    }

  }

  return fakeHead.next;

}

19. Remove Nth Node From End of List
删除链表的倒数第n个结点。思路：因为单向链表是没有前驱指针的，所以应找到倒数第n+1个结点；n有可能等于链表的长度，故先new一个head的前驱结点fakeHead。用两个指针slow、fast从fakeHead开始，先移动fast n+1步，使得其距离slow为n+1；然后，两个指针同步移动，当fast走到null时，slow即处于倒数第n+1个结点，删除slow的next结点即可。

public ListNode removeNthFromEnd(ListNode head, int n) {

  ListNode fakeHead = new ListNode(Integer.MIN_VALUE);

  fakeHead.next = head;

  ListNode slow = fakeHead, fast = fakeHead;

  for (int i = 1; i <= n + 1; i++) {

    fast = fast.next;

  }

  while(fast != null) {

    fast = fast.next;

    slow = slow.next;

  }

  slow.next = slow.next.next; // the n-th node from end is `slow.next`

  return fakeHead.next;

}

83. Remove Duplicates from Sorted List
删除有序链表中的重复元素。处理思路有上一问题类似，不同的是判断删除的条件。

public ListNode deleteDuplicates(ListNode head) {

  ListNode fakeHead = new ListNode(Integer.MIN_VALUE);

  fakeHead.next = head;

  for (ListNode curr = head, prev = fakeHead; curr != null && curr.next != null; curr = curr.next) {

    if (curr.val == curr.next.val) { // remove

      prev.next = curr.next;

    } else {

      prev = prev.next;

    }

  }

  return fakeHead.next;

}

82. Remove Duplicates from Sorted List II
上一问题的升级版，删除所有重复元素结点。在里层增加一个while循环，跳过重复元素结点。

public ListNode deleteDuplicates(ListNode head) {

  ListNode fakeHead = new ListNode(Integer.MIN_VALUE);

  fakeHead.next = head;

  for (ListNode curr = head, prev = fakeHead; curr != null; curr = curr.next) {

    while (curr.next != null && curr.val == curr.next.val) { // find the last duplicate

      curr = curr.next;

    }

    if (prev.next == curr) prev = prev.next;

    else prev.next = curr.next;

  }

  return fakeHead.next;

}

24. Swap Nodes in Pairs
链表中两两交换。按step = 2 遍历链表并交换；值得注意的是在更新next指针是有次序的。

public ListNode swapPairs(ListNode head) {

  ListNode fakeHead = new ListNode(Integer.MIN_VALUE);

  fakeHead.next = head;

  for (ListNode prev = fakeHead, p = head; p != null && p.next != null; ) {

    ListNode temp = p.next.next;

    prev.next = p.next; // update next pointer

    p.next.next = p;

    p.next = temp;

    prev = p;

    p = temp;

  }

  return fakeHead.next;

}

206. Reverse Linked List
逆序整个链表。逆序操作可以看作：依次遍历链表，将当前结点插入到链表头。

public ListNode reverseList(ListNode head) {

  ListNode newHead = null;

  for (ListNode curr = head; curr != null; ) {

    ListNode temp = curr.next;

    curr.next = newHead; // insert to the head of list

    newHead = curr;

    curr = temp;

  }

  return newHead;

}

92. Reverse Linked List II
上一问题的升级，指定区间[m, n]内做逆序；相当于把该区间的链表逆序后，再拼接到原链表中。

public ListNode reverseBetween(ListNode head, int m, int n) {

  ListNode newHead = null, curr = head, firstHead = null, firstHeadPrev = null;

  for (int i = 1; curr != null && i <= n; i++) {

    if (i < m - 1) {

      curr = curr.next;

      continue;

    }

    if (i == m - 1) {

      firstHeadPrev = curr; // mark first head previous node

      curr = curr.next;

    } else {

      if (i == m) firstHead = curr; // mark first head node

      ListNode temp = curr.next;

      curr.next = newHead;

      newHead = curr;

      curr = temp;

    }

  }

  firstHead.next = curr;

  if (firstHeadPrev != null) firstHeadPrev.next = newHead;

  if (m == 1) return newHead;

  return head;

}

61. Rotate List
指定分隔位置，将链表的左右部分互换。只需修改左右部分的最后节点的next指针即可，有一些special case需要注意，诸如：链表为空，k为链表长度的倍数等。为了得到链表的长度，需要做一次pass。故总共需要遍历链表两次。

public ListNode rotateRight(ListNode head, int k) {

  if (head == null || k == 0) return head;

  int n = 0, i;

  ListNode curr, leftLast = head, rightFist, rightLast = head;

  for (curr = head; curr != null; curr = curr.next) { // get the length of list

    n++;

  }

  k %= n; // k maybe larger than n

  if (k == 0) return head;

  for (i = 1, curr = head; i <= n; i++, curr = curr.next) { // mark the split node

    if (i == n - k) leftLast = curr;

    if (i == n) rightLast = curr;

  }

  rightFist = leftLast.next;

  leftLast.next = null;

  rightLast.next = head;

  return rightFist;

}

86. Partition List
类似于quick sort的partition，不同的是要保持链表的原顺序。思路：用两个链表，一个保留小于指定数x，一个保留不大于指定数x；最后拼接到一起即可。

public ListNode partition(ListNode head, int x) {

  if (head == null) return null;

  ListNode lt = new ListNode(-1), gte = new ListNode(-2); // less than, greater than and equal

  ListNode p, p1, p2;

  for (p = head, p1 = lt, p2 = gte; p != null; p = p.next) {

    if (p.val < x) {

      p1.next = p;

      p1 = p1.next;

    } else {

      p2.next = p;

      p2 = p2.next;

    }

  }

  p2.next = null;

  p1.next = gte.next;

  return lt.next;

}

328. Odd Even Linked List
链表分成两部分：偶数编号与奇数编号，将偶数链表拼接到奇数链表的后面。

public ListNode oddEvenList(ListNode head) {

  if (head == null || head.next == null) return head;

  ListNode odd = head, even = head.next, evenHead = head.next;

  while (odd.next != null && odd.next.next != null) {

    odd.next = odd.next.next;

    odd = odd.next;

    if (even != null && even.next != null) {

      even.next = even.next.next;

      even = even.next;

    }

  }

  odd.next = evenHead; // splice even next to odd

  return head;

}

21. Merge Two Sorted Lists
合并两个有序链表。比较简单，分情况比较。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

  ListNode head = new ListNode(-1), p, p1, p2;

  for (p = head, p1 = l1, p2 = l2; p1 != null || p2 != null; p = p.next) {

    if (p1 != null) {

      if (p2 != null && p1.val > p2.val) {

        p.next = p2;

        p2 = p2.next;

      } else {

        p.next = p1;

        p1 = p1.next;

      }

    } else {

      p.next = p2;

      p2 = p2.next;

    }

  }

  return head.next;

}

23. Merge k Sorted Lists
合并k个有序链表。思路：借助于堆，堆的大小为k，先将每个链表的首结点入堆，堆顶元素即为最小值，堆顶出堆后将next入堆；依此往复，即可得到整个有序链表。

public ListNode mergeKLists(ListNode[] lists) {

  if (lists.length == 0) return null;

  PriorityQueue<ListNode> minHeap = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {

    @Override

    public int compare(ListNode o1, ListNode o2) {

      return o1.val - o2.val;

    }

  });

  // initialization

  for (ListNode node : lists) {

    if (node != null)

      minHeap.offer(node);

  }

  ListNode head = new ListNode(-1);

  for (ListNode p = head; !minHeap.isEmpty(); ) {

    ListNode top = minHeap.poll();

    p.next = top;

    p = p.next;

    if (top.next != null)

      minHeap.offer(top.next);

  }

  return head.next;

}

141. Linked List Cycle
判断链表是否有环。用两个指针，一个快指针一个慢指针，一个每次移动两步，一个每次移动一步；最后两者相遇，即说明有环。

public boolean hasCycle(ListNode head) {

  if (head == null) return false;

  for (ListNode slow = head, fast = head; fast.next != null && fast.next.next != null; ) {

    slow = slow.next;

    fast = fast.next.next;

    if (slow == fast) return true;

  }

  return false;

}

142. Linked List Cycle II
找出链表中环的起始节点s。解决思路：用两个指针——fast、slow，先判断是否环；两者第一次相遇的节点与ss的距离 == 链表起始节点与s的距离（有兴趣可以证明一下）。

public ListNode detectCycle(ListNode head) {

  if (head == null || head.next == null) return null;

  ListNode slow = head, fast = head;

  boolean isCycled = false;

  while (slow != null && fast != null && fast.next != null) { // first meeting

    slow = slow.next;

    fast = fast.next.next;

    if (slow == fast) {

      isCycled = true;

      break;

    }

  }

  if (!isCycled) return null;

  for (fast = head; slow != fast; ) { // find the cycle start node

    slow = slow.next;

    fast = fast.next;

  }

  return slow;

}

234. Palindrome Linked List
判断链表LL是否中心对称。中心对称的充分必要条件：对于任意的 i <= n/2 其中n为链表长度，有L[i] = L[n+1-i]成立。因此先找出middle结点（在距离首结点n/2处），然后逆序右半部分链表，与左半部分链表的结点一一比较，即可得到结果。在找出middle结点时也用到了小技巧——快慢两个指针遍历链表，当fast遍历完成时，slow即为middle结点（证明分n为奇偶情况）；当n为偶数时，middle结点有两个，此时slow为左middle结点。换句话说，无论n为奇数或偶数，此时的slow为右半部分子链表的第一个结点的前驱结点。

public boolean isPalindrome(ListNode head) {

  if (head == null) return true;

  ListNode slow = head, fast = head, p;

  while (fast.next != null && fast.next.next != null) {

    slow = slow.next;

    fast = fast.next.next;

  }

  ListNode q = reverseList(slow.next); // the first node of the right half is `slow.next`

  for (p = head; q != null; p = p.next, q = q.next) {

    if (p.val != q.val) return false;

  }

  return true;

}

143. Reorder List
对于除去首结点外的链表，将右半部分子链表从后往前依次插入进左半部分链表。解决思路与上类似，找出middle结点，然后依次插入。值得注意：Java的对象传参是引用类型，需要更新左半部份子链表的最后一个结点的next指针，不然则链表的结点的无限循环导致OOM。

public void reorderList(ListNode head) {

  if (head == null || head.next == null) return;

  ListNode slow = head.next, fast = head.next;

  while (fast.next != null && fast.next.next != null) {

    slow = slow.next;

    fast = fast.next.next;

  }

  ListNode p, q = reverseList(slow.next);

  slow.next = null; // update the next pointer of the left half's last node

  for (p = head; q != null; ) {

    ListNode pNext = p.next, qNext = q.next;

    p.next = q; // insert qNode into the next of p node

    q.next = pNext;

    p = pNext;

    q = qNext;

  }

}

160. Intersection of Two Linked Lists
求两个链表相交的第一个结点P。假定两个链表的长度分别为m、n，相交的第一个结点PP分别距离两个链表的首结点为a、b，则根据链表相交的特性：两个链表的尾节点都是同一个，即m-a = n-b；移项后有m+b = n+a。根据上述性质，在遍历完第一个链表后，再往右b个结点，即到达了结点P。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

  if (headA == null || headB == null) return null;

  ListNode ptrA = headA, ptrB = headB;

  while (ptrA != ptrB) { // in case ptrA == ptrB == null

    ptrA = (ptrA != null) ? ptrA.next : headB;

    ptrB = (ptrB != null) ? ptrB.next : headA;

  }

  return ptrA;

}

2. Add Two Numbers
模拟两个链表的加法。开始的时候没理解清楚题意，被坑了多次WA。链表的head表示整数的个位，则应从首端对齐开始做加法。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

  ListNode head = new ListNode(-1);

  boolean carry = false; // mark whether has carry

  for (ListNode p = l1, q = l2, r = head; p != null || q != null || carry; r = r.next) {

    int pVal = (p == null) ? 0 : p.val;

    int qVal = (q == null) ? 0 : q.val;

    int sum = carry ? pVal + qVal + 1 : pVal + qVal;

    carry = sum >= 10;

    r.next = new ListNode(sum % 10);

    if (p != null) p = p.next;

    if (q != null) q = q.next;

  }

  return head.next;

}

445. Add Two Numbers II
与上一题不同的是，链表的head表示整数的最高位，则应是尾端对齐相加。为了尾端对齐，将采用stack来逆序链表，之后相加步骤与上类似；但创建新链表应使用头插法。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

  ListNode p;

  Stack<Integer> s1 = new Stack<>();

  Stack<Integer> s2 = new Stack<>();

  for (p = l1; p != null; p = p.next) {

    s1.push(p.val);

  }

  for (p = l2; p != null; p = p.next) {

    s2.push(p.val);

  }

  ListNode head = new ListNode(-1);

  boolean carry = false; // mark whether has carry

  for (ListNode r = null; !s1.isEmpty() || !s2.isEmpty() || carry; ) {

    int pVal = (s1.isEmpty()) ? 0 : s1.pop();

    int qVal = (s2.isEmpty()) ? 0 : s2.pop();

    int sum = carry ? pVal + qVal + 1 : pVal + qVal;

    carry = sum >= 10;

    ListNode node = new ListNode(sum % 10);

    node.next = r;

    head.next = node;

    r = node;

  }

  return head.next;

}

如需转载，请注明作者及出处.

作者：Treant

出处：http://www.cnblogs.com/en-heng/