链表题总结（以LeetCode为主）

237. Delete Node in a Linked List Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function. 给出一个方法，此方法能够删除指定的节点。 分析：本来打算从头开始遍历，找到此节点的前一个节点，然后p.next = p.next.next；就能把此节点删除掉，但是发现此题目没有头节点，所以这个想法只能作废。而且此方法的时间复杂度为O(n)。所以值覆盖法，看似是把当前节点删除了，其实是把后一个节点的所有实例变量赋值给要删除的节点，然后把后一个节点给从链表中删除了，时间复杂度为O(1)。

public class Solution { public void deleteNode(ListNode node) { if(node.next != null){ node.val = node.next.val; node.next = node.next.next; } } }

203. Remove Linked List Elements Remove all elements from a linked list of integers that have value val.

Example Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6 Return: 1 –> 2 –> 3 –> 4 –> 5 删除链表中指定值的节点。 分析：表头跟表中的元素不是一个删除法，表中的元素记录它的前继节点p，p.next = p.next.next；将要删除的节点越过，便可以从链表中删除此节点。而表头的节点因为没有前继节点，只能head = head.next;将头节点往后移一个节点。所以此题分两步进行。

public class Solution { public ListNode removeElements(ListNode head, int val) { //先处理表头节点 while(head != null && head.val == val) head = head.next; ListNode p = head; //处理表中节点，设置pre为要删除节点的前继 for(ListNode pre = head; head!=null; head = head.next){ if(head.val == val) pre.next = head.next; else pre = head; } return p; } }

83. Remove Duplicates from Sorted List Given a sorted linked list, delete all duplicates such that each element appear only once.

For example Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3. 分析：此题只要将相同的元素删除，如果有和头结点值相同的节点，只需要将后面的节点删除即可，所以不用单独考虑头节点。

public class Solution { public ListNode deleteDuplicates(ListNode head) { if(head == null) return null; for(ListNode pre = head,p = head.next; p!=null;p=p.next){ if(pre.val == p.val) pre.next = p.next; else pre = p; } return head; } }

234. Palindrome Linked List Given a singly linked list, determine if it is a palindrome. Follow up: Could you do it in O(n) time and O(1) space? 给一个单链表，判断此链表是否是回文。并且能够做到时间复杂度为O(n)，空间复杂度为O(1)。 分析：回文的定义就是将一串字符串反转后，字符序列跟反转前一样。如12321等。所以首先想到的是，从头遍历链表，以前插法新建一个链表，newnode.next=head;head=newnode;这样新建的链表就和以前的链表反序，然后遍历判断两者是否相等，时间复杂度为O(n)，但空间复杂度为O(n)。 此方法作废，另辟蹊径。细读题目，发现题目并没有要求保持原链表的数据结构，所以可以在原链表的数据结构上进行改变，判断。将后半段进行反转，前后两段判断是否相等即可。 首先让我们认识一下原地反转： 1、将每一个节点（处头节点外）指望它的前继。 2、调整链表的表头和表尾。 代码如下：

public ListNode Rerseve(ListNode head){ if(head == null) return null; ListNode pre = head; ListNode pse = head.next; while(pse != null){ ListNode t = pse.next; pse.next = pre; pre = pse; pse = t; } head.next = null; return pre; }

其次，我们还需要找到后半段反转的第一个节点。这里就涉及到了快慢指针（slow），快指针（fast）每次走两步，慢指针每次走一步，这样快指针走到表尾的时候，慢指针正好走到表中。而且慢指针的下一个节点就是要反转的后半段的第一个节点。 综上，此题的解题代码为：

/** *原地反转 * 时间复杂度O(n)，空间复杂度是O(1) */ public class Solution { public boolean isPalindrome(ListNode head) { boolean is_not = true; ListNode fast = head; ListNode slow = head; //链表为空或者链表只有一个元素 if(head==null || head.next ==null) return is_not ; //寻找反转后半部分的第一个节点，同时还要保存此节点的前继， //所以循环的终止条件不是fast!=null&&fast.next!=null while(fast.next != null && fast.next.next != null){ fast = fast.next.next; slow = slow.next; } //后半段反转 ListNode pReversed = slow.next;//要反转的第一个节点 ListNode pre = slow;//反转节点前一个节点 ListNode t; while(pReversed != null){ t = pReversed.next; pReversed.next = pre; pre = pReversed; pReversed = t; } //重定向头尾指针 slow.next.next = null; slow.next = pre; //前半段和后半段比较 for(ListNode p = slow.next ; p != null; p = p.next){ if(head.val != p.val) return is_not = false; head = head.next; } return is_not; } }

206. Reverse Linked List Reverse a singly linked list. 上题判断是否是回文中已经讲到了，自行翻阅。

/** * 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; ListNode pre = head; for(ListNode p = head.next; p!= null; ){ ListNode t = p.next; p.next = pre; pre = p; p = t; } head.next = null; return pre; } }

160. Intersection of Two Linked Lists Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists:

Notes: If the two linked lists have no intersection at all, return null. The linked lists must retain their original structure after the function returns. You may assume there are no cycles anywhere in the entire linked structure. Your code should preferably run in O(n) time and use only O(1) memory.

判断两个链表是否相交，并且找到第一相交的节点。 分析：首先想到的是两层for循环，寻找两者的共同节点，如果有的话则返回此节点，没有的话返回null。但是此方法的时间复杂度O(n^2)，明显的超时。 所以得想办法缩减寻找共同节点的时间，经分析不难知道，如果两个链表如果相交也肯定是后半部分相交，即将两个链表尾对齐。分两层循环，第一遍循环，找到两个链表的表长之差length，让相较较长的链表先行length；第二遍循环，两个链表一起前进、比较，若找到两个相同的节点，则表明两个链表有相交的部分，返回此节点，若两个链表到尾部还没找到，说明两个链表不想交，返回null。时间复杂度为O(n)。

/** * 第一遍循环找到长度差N * 第二遍循环，长链表先走N步，然后同时移动，判断是否有相同节点 * */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode node = null; int lengthA = 0; int lengthB = 0; boolean is_find = false; ListNode startA = headA; ListNode startB = headB; while(startA != null && startB != null){ startA = startA.next; startB = startB.next; } while(startA != null) { startA = startA.next; ++lengthA; } while(startB != null){ startB = startB.next; ++lengthB; } //比较长的链表先行 startA = headA; startB = headB; while( --lengthA >= 0) startA = startA.next; while( --lengthB >= 0) startB = startB.next; //开始比较两个节点 while(startA != null && startB != null){ if(startA == startB) return startA; startA = startA.next; startB = startB.next; } return node; }

又做了一遍，发现这次的方法更简单一些：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode p1 = headA, p2 = headB; int num = 0; while (p1 != null && p2 != null){ p1 = p1.next; p2 = p2.next; } ListNode pheadA = headA, pheadB = headB; while (p1 != null && pheadA!=null){ pheadA = pheadA.next; p1 = p1.next; } while (p2 != null && pheadB!=null){ pheadB = pheadB.next; p2 = p2.next; } while (pheadA != null && pheadB!=null){ if(pheadA == pheadB){ return pheadA; } else{ pheadA = pheadA.next; pheadB = pheadB.next; } } return null; }

141. Linked List Cycle Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

判断一个单链表是否有环，并且不借用额外的空间。 分析：依旧用到了链表的老朋友，快（fast）慢（slow）指针。如果有环快慢指针肯定会相遇。

public class Solution { public boolean hasCycle(ListNode head) { boolean is_has = false; if(head == null) return is_has; ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow) return is_has = true; } return is_has; } }

142. Linked List Cycle II Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up: Can you solve it without using extra space?

Subscribe to see which companies asked this question. 判断一个链表是否有环，并找到环的第一个节点，即环的入口节点。 这篇博客将用快慢指针寻找环入口节点解释的非常详细 即从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点。所以这儿我只贴出我自己写的代码：

public class Solution { public ListNode detectCycle(ListNode head) { if(head == null) return null; ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow){ slow = head; while(true){ if(slow == fast) return slow; slow = slow.next; fast = fast.next; } } } return null; } }

21. Merge Two Sorted Lists Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

分析:将两个已排好序的链表连接成一个排好序的链表。 算法步骤：1、指针phead1和phead2初始化，分别指向l1和l2的第一个节点。 2、phead指向新建的头结点。 3、当phead1和phead2均未到达相应的表尾时，则依次比较phead1和 phead2所指向的节点的值，从l1和l2中“摘取”节点值最小的节点插入到phead后面。 4、将非空表的剩余段插入到phead所指的节点后。 5、返回head.next。

public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null && l2 == null) return null; ListNode phead1 = l1; ListNode phead2 = l2; ListNode head = new ListNode(-1); ListNode phead = head; while(phead1 != null && phead2 != null){ if(phead1.val <= phead2.val){ phead.next = phead1; phead = phead1; phead1 = phead1.next; } else { phead.next = phead2; phead = phead2; phead2 = phead2.next; } } while (phead1 != null) { phead.next = phead1; phead = phead1; phead1 = phead1.next; } while (phead2 != null){ phead.next = phead2; phead = phead2; phead2 = phead2.next; } return head.next; } }