1.删除链表中的节点

image.png

1.1解答

image.png

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. class Solution {
  10.     public void deleteNode(ListNode node) {
  11.         //把要删除结点的下一个结点的值赋给要删除的结点
  12.         node.val = node.next.val;
  13.         //然后删除下一个结点
  14.         node.next = node.next.next;
  15.     }
  16. }

2.单向反转链表

image.png

2.1使用递归解决√

  1. public ListNode reverseList(ListNode head) {
  2.     //终止条件
  3.     if (head == null || head.next == null)
  4.         return head;
  5.     //保存当前节点的下一个结点
  6.     ListNode next = head.next;
  7.     //从当前节点的下一个结点开始递归调用
  8.     ListNode reverse = reverseList(next);
  9.     /*reverse是反转之后的链表，因为函数reverseList
  10.      表示的是对链表的反转，所以反转完之后next肯定
  11.      是链表reverse的尾结点，然后我们再把当前节点*/
  13.     //head挂到next节点的后面就完成了链表的反转。
  14.     next.next = head;
  15.     //这里head相当于变成了尾结点，尾结点都是为空的，
  16.     //否则会构成环
  17.     head.next = null;
  18.     return reverse;
  19. }
  21. -------------------------------------------------------------
  22. 自己的想法:
  23.     /**
  24.  * Definition for singly-linked list.
  25.  * public class ListNode {
  26.  *     int val;
  27.  *     ListNode next;
  28.  *     ListNode() {}
  29.  *     ListNode(int val) { this.val = val; }
  30.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  31.  * }
  32.  */
  33. class Solution {
  34.     public ListNode reverseList(ListNode head) {
  35.         //定位到末结点
  36.         if(head.next==null||head==null)
  37.             return head;
  38.         //3->4->5->1 假如当前head=node3,reverseList(head.next)=reverseList(node4)=node4=newHead
  39.         ListNode newHead = reverseList(head.next);
  40.         head.next.next = head;//即node4.next=node3
  41.         head.next=null;//即node3.next=null 实现: node4->node3->null
  42.         return newHead;
  43.     }
  44. }

2.2尾递归*

  1. public ListNode reverseList(ListNode head) {
  2.     return reverseListInt(head, null);
  3. }
  5. private ListNode reverseListInt(ListNode head, ListNode newHead) {
  6.     if (head == null)
  7.         return newHead;
  8.     ListNode next = head.next;
  9.     head.next = newHead;
  10.     return reverseListInt(next, head);
  11. }

2.3使用栈解决

image.png

  1. class Solution {
  2.    public ListNode reverseList(ListNode head) {
  3.        Stack<ListNode> stack = new Stack<>();
  4.        //将每个结点放入栈中
  5.        while(head!=null){
  6.            stack.push(head);
  7.            head = head.next; 
  8.        }
  9.        //若栈为空，即没有结点，返回null
  10.         if (stack.isEmpty())
  11.         return null;
  12.        //以第一个弹出的结点为头结点
  13.        ListNode node = stack.pop();
  14.        ListNode newHead = node;
  15.        //依次弹栈接入头结点尾后
  16.        while(!stack.isEmpty()){
  17.            ListNode temp = stack.pop();
  18.            node.next=temp;
  19.            node = node.next;
  20.        }
  21.        //让尾结点的next为null
  22.        node.next = null;
  23.        return newHead;
  24.    }
  25. }

2.4双链表求解

image.png

  1. class Solution {
  2.    public ListNode reverseList(ListNode head) {
  3.        ListNode newHead = null;
  4.        while(head!=null){
  5.         //先保存访问的节点的下一个节点，保存起来留着下一步访问的
  6.         ListNode temp = head.next;
  7.         //每次访问的原链表节点都会成为新链表的头结点，其实就是把新链表挂到访问的原链表节点的后面就行了
  8.         head.next = newHead;
  9.         //更新新链表
  10.         newHead = head;
  11.         //重新赋值，继续访问
  12.         head = temp;
  13.        }
  14.        return newHead;
  15.    }
  16. }
  18. ----------------------------------------------------------------
  19. class Solution {
  20.    public ListNode reverseList(ListNode head) {
  21.        ListNode newHead = null;
  22.        while(head!=null){
  23.            ListNode temp = head.next;
  25.            head.next=newHead;//核心
  26.            newHead=head;
  28.            head=temp;
  29.        }
  30.        return newHead;
  31.    }
  32. }

3.合并两个有序链表

image.png

3.1解法一√

因为链表是升序的，我们只需要遍历每个链表的头，比较一下哪个小就把哪个链表的头拿出来放到新的链表中，一直这样循环，直到有一个链表为空，然后我们再把另一个不为空的链表挂到新的链表中。
以3→4→7→9和2→5→6两个链表来画个图看一下是怎么合并的。
image.png

  1.     public ListNode mergeTwoLists(ListNode linked1, ListNode linked2) {
  3.         if (linked1 == null)
  4.             return linked2;
  5.         if (linked2 == null)
  6.             return linked1;
  8.         ListNode dummy = new ListNode(0);
  9.         ListNode curr = dummy;//两结点地址相同，修改curr的后续就相当于修改dummy的后续
  10.         while (linked1 != null && linked2 != null) {
  11.             //比较一下，哪个小就把哪个放到新的链表中
  12.             if (linked1.val <= linked2.val) {
  13.                 curr.next = linked1;
  14.                 linked1 = linked1.next;
  15.             } else {
  16.                 curr.next = linked2;
  17.                 linked2 = linked2.next;
  18.             }
  19.             curr = curr.next;
  20.         }
  21.         //然后把那个不为空的链表挂到新的链表中
  22.         curr.next = linked1 == null ? linked2 : linked1;
  23.         return dummy.next;
  24.     }

3.2解法二递归（难理解）

image.png

  1.     public ListNode mergeTwoLists(ListNode linked1, ListNode linked2) {
  2.         if (linked1 == null)
  3.             return linked2;
  4.         if (linked2 == null)
  5.             return linked1;
  6.         if (linked1.val < linked2.val) {
  7.             linked1.next = mergeTwoLists(linked1.next, linked2);
  8.             return linked1;
  9.         } else {
  10.             linked2.next = mergeTwoLists(linked1, linked2.next);
  11.             return linked2;
  12.         }
  13.     }
  16. --------------------------------------------------------------
  17.         public ListNode mergeTwoLists(ListNode linked1, ListNode linked2) {
  18.         if (linked1 == null || linked2 == null)
  19.             return linked2 == null ? linked1 : linked2;
  20.         ListNode first = (linked2.val < linked1.val) ? linked2 : linked1;
  21.         first.next = mergeTwoLists(first.next, first == linked1 ? linked2 : linked1);
  22.         return first;
  23.     }

4.判断回文链表

image.png

4.1使用栈解决（简易）

  1. class Solution {
  2.     public boolean isPalindrome(ListNode head) {
  3.         Stack<Integer> stack = new Stack<>();
  4.         ListNode temp = head;
  5.         while(temp!=null){
  6.             stack.push(temp.val);
  7.             temp=temp.next;
  8.         }
  9.         boolean flag = true;
  10.         while(head!=null){
  11.             if(head.val!=stack.pop()){
  12.                 flag=false;
  13.             }
  14.             head=head.next;
  15.         }
  16.         return flag;
  17.     }
  18. }

这里相当于链表从前往后全部都比较了一遍，其实我们只需要拿链表的后半部分和前半部分比较即可，没必要全部比较，所以这里可以优化一下

  1. public boolean isPalindrome(ListNode head) {
  2.     if (head == null)
  3.         return true;
  4.     ListNode temp = head;
  5.     Stack<Integer> stack = new Stack();
  6.     //链表的长度
  7.     int len = 0;
  8.     //把链表节点的值存放到栈中
  9.     while (temp != null) {
  10.         stack.push(temp.val);
  11.         temp = temp.next;
  12.         len++;
  13.     }
  14.     //len长度除以2
  15.     len >>= 1;
  16.     //然后再出栈
  17.     while (len-- >= 0) {
  18.         if (head.val != stack.pop())
  19.             return false;
  20.         head = head.next;
  21.     }
  22.     return true;
  23. }

4.2反转后半部分链表（较难）

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public boolean isPalindrome(ListNode head) {
  13.     ListNode fast = head, slow = head;//假设链表为1->2->3->4->3->2->1
  14.     //通过快慢指针找到中点
  15.     while (fast != null && fast.next != null) {
  16.         fast = fast.next.next;
  17.         slow = slow.next;
  18.         //1->2->3->4->3->2->1 fast=3 slow=2 - fast=3 slow=3 - fast=1 slow=4 fasst.next=null 结束循环
  19.     }
  21.     //如果fast不为空，说明链表的长度是奇数个
  22.     if (fast != null) {//fast=node7 !=null 长度为奇数,slow=slow.next=node5
  23.         slow = slow.next; 
  24.     }
  25.     //反转后半部分链表
  26.     slow = reverse(slow);//反转后结果为1->2->3->null
  28.     fast = head;//将快指针重新指向head 用于判断前半部分与后半部分是否相同
  29.     while (slow != null) {
  30.         //然后比较，判断节点值是否相等
  31.         if (fast.val != slow.val)
  32.             return false;
  33.         fast = fast.next;
  34.         slow = slow.next;
  35.     }
  36.     return true;
  37. }
  39. //反转链表
  40. public ListNode reverse(ListNode head) {//假如后半部分传来的链表为3->2->1->null
  41.    while(head==null||head.next==null){
  42.        return head;
  43.    }
  44.    ListNode newHead = reverse(head.next);//2.next!=null 当前为head2 newHead=1
  45.    head.next.next=head;//1->2
  46.    head.next=null;//1->2->null
  47.    return newHead;
  48. }
  49. }

总结：通过快慢指针找到后半部分链表，反转后半部分链表（也是可以考虑用栈的思想），将前后部分链表进行对比，如果结点都相同，则该链表为回文链表。

5.判断环形链表

5.1快慢指针

  1. public boolean hasCycle(ListNode head) {
  2.         if(head==null){
  3.              return false;
  4.         }
  5.         ListNode slow = head;
  6.         ListNode fast = head;
  7.         while(fast!=null&&fast.next!=null){
  8.             slow=slow.next;
  9.             fast=fast.next.next;
  10.             if(slow==fast){
  11.                 return true;
  12.             }
  13.         }
  14.         return false;
  15.     }