解题思路

1 快慢指针，有时候要用到三个指针
2 构建一个虚假的链表头

2. 两数相加

https://leetcode-cn.com/problems/add-two-numbers/

package main
import (
    "fmt"
    "strings"
)
type ListNode struct {
    Val int
    Next *ListNode
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummyHead := &ListNode{Val:0}
    p :=l1
    q :=l2
    curr := dummyHead
    carry := 0
    for p!=nil||q!=nil  {
        var x,y int
        if p!=nil {
            x =p.Val
        }
        if q!=nil {
            y =q.Val
        }
        sum :=carry+x+y
        carry = sum/10
        node :=&ListNode{Val:sum%10}
        curr.Next = node
        curr = node
        if p!=nil{
            p = p.Next
        }
        if q !=nil{
            q =q.Next
        }
    }
    if carry>0{
       curr.Next = &ListNode{Val:carry}
    }
   return dummyHead.Next
}
func main() {
    l1:= &ListNode{Val:2,Next:&ListNode{Val:4,Next:&ListNode{Val:3}}}
    l2:= &ListNode{Val:5,Next:&ListNode{Val:6,Next:&ListNode{Val:4}}}
    r := addTwoNumbers(l1,l2)
    curr := r
    var str strings.Builder
    for curr!=nil{
        str.WriteString(fmt.Sprintf("%d -> ",curr.Val))
        curr = curr.Next
    }
    fmt.Println(strings.TrimRight(str.String()," -> "))
}

package main

import (
    "fmt"
    "strings"
)

type ListNode struct {
    Val int
    Next *ListNode
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    head := &ListNode{}
    p := l1
    q := l2
    currentHead := head
    var sum,carry int
    for true  {
         if q != nil || p != nil {
             var x,y int
             if p!=nil {
                 x=p.Val
                 p = p.Next
             }
             if q!=nil {
                 y =q.Val
                 q = q.Next
             }

            sum = carry + x + y
            carry = sum / 10
        } else {
            break
        }
        currentHead.Val = sum % 10
        if p!=nil||q!=nil {
            currentHead.Next = &ListNode{}
            currentHead = currentHead.Next
        }

    }
    if carry != 0 {
        currentHead.Next = &ListNode{carry, nil}
    }
    return head
}

func main() {
    l1:= &ListNode{Val:2,Next:&ListNode{Val:4,Next:&ListNode{Val:3}}}
    l2:= &ListNode{Val:5,Next:&ListNode{Val:6,Next:&ListNode{Val:4}}}
    r := addTwoNumbers(l1,l2)
    curr := r
    var str strings.Builder
    for curr!=nil{
        str.WriteString(fmt.Sprintf("%d -> ",curr.Val))
        curr = curr.Next
    }
    fmt.Println(strings.TrimRight(str.String()," -> "))
}

160. 相交链表

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：

在节点 c1 开始相交。
示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

设置快慢指针

public ListNode getIntersectionNode (ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode p1 = headA;
    ListNode p2 = headB;
    while (p1 != p2) {
        if (p1 == null) p1 = headB;
        else p1 = p1.next;
        if (p2 == null) p2 = headA;
        else p2 = p2.next;
    }
    return p1;
}

203. 移除链表元素

https://leetcode-cn.com/problems/remove-linked-list-elements/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
          ListNode dummyHead = new ListNode(-1);
            ListNode currNode = dummyHead;
            while (head!=null){
                if (head.val!=val){
                    currNode.next = head;
                    currNode = currNode.next;
                }
                head = head.next;
            }
            currNode.next = null;
          return dummyHead.next;
    }
}

206. 反转链表

递归法：

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

迭代法：

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

通过哑结点方式实现，重新创建一个新的链表，每次往头部插入数据，而不是尾部插入数据，
go语言实现

func reverseList(head *ListNode) *ListNode {
    if head == nil||head.Next==nil{
        return head
    }
    dummyNode := &ListNode{}// 哑结点
    cur := head
    for cur != nil{
        next := cur.Next // 为了遍历，临时变量存储当前节点的下一个节点
        head :=  dummyNode.Next // 临时变量存储当前哑结点的指向的头结点
        dummyNode.Next = cur // 往头部插入数据,当前节点变成了头结点了
        cur.Next = head // 为了维持链条 需要把之前的头结点变成下一个节点
        cur = next // 遍历移动
    }
    return dummyNode.Next // 返回头结点
}

21. 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

双指针思想

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if(l1 == null) return l2;
    if(l2 == null) return l1;
    if(l1.val < l2.val){
        l1.next = mergeTwoLists(l1.next,l2);
        return l1;
    }else{
        l2.next = mergeTwoLists(l1,l2.next);
        return l2;
    }
}

83. 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

一次遍历，注意边界条件。

public ListNode deleteDuplicates(ListNode head) {
    ListNode cur = head;
    while(cur != null && cur.next != null){
        if(cur.val == cur.next.val)
            cur.next = cur.next.next;
        else
            cur = cur.next;
    }
    return head;
}

19. 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？

type ListNode struct {
     Val int
     Next *ListNode
 }

func removeNthFromEnd(head *ListNode, n int) *ListNode {
      //dump node
      d := &ListNode{Next:head}
      len :=0
      first := head
      for first!=nil{
          first = first.Next
          len++
      }
      len =len-n// revert index
      first = d
      for len >0{
          len--
          first = first.Next
      }
      first.Next = first.Next.Next
      return d.Next
}

func main() {
    head := &ListNode{Val:1}
    head.Next = &ListNode{Val:2}
    node := head.Next
    node.Next = &ListNode{Val:3}
    node = node.Next
    node.Next = &ListNode{Val:4}
    node = node.Next
    node.Next = &ListNode{Val:5}
    d := removeNthFromEnd(head,2)
    for  d!=nil {
        fmt.Println(d.Val)
        d = d.Next
    }
}

设置哑节点1，让它走 n+1 步，再设置哑节点2，然后哑节点1和哑节点2一起移动，直到哑节点1走完链表，此时哑节点1和哑节点2之间正好隔着 n 个节点，再通过哑节点2删除倒数第 n 个节点。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    for (int i = 1; i <= n + 1;i++){
        first = first.next;
    }
    ListNode second = dummy;
    while(first != null){
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

234. 回文链表

请判断一个链表是否为回文链表。
示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

设置快慢指针，移动速度分别是2和1。当快指针到达链表尾部的时候，慢指针就在正中间（奇数个节点的情况下）或者正中间的左边（偶数个节点的情况下），再将慢指针向后移动一位，反转以慢指针为头的链表，再逐个节点对比是否相等。

public boolean isPalindrome (ListNode head) {
    if (head == null || head.next == null) return true;
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    slow = slow.next;
    slow = reverse(slow);
    while (slow != null) {
        if (head.val == slow.val) {
            head = head.next;
            slow = slow.next;
        } else
            return false;
    }
    return true;
}
private ListNode reverse (ListNode head) {
    ListNode newHead = null;
    while (head != null) {
        ListNode nextNode = head.next;
        head.next = newHead;
        newHead = head;
        head = nextNode;
    }
    return newHead;
}

24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

设置哑节点，注意循环条件，指针移动的速度是2（因为需要两两交换节点）。

public ListNode swapPairs (ListNode head) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode pre = dummy;
    while (pre.next != null && pre.next.next != null) {
        ListNode l1 = pre.next;
        ListNode l2 = pre.next.next;
        l1.next = l2.next;
        l2.next = l1;
        pre.next = l2;
        pre = l1;
    }
    return dummy.next;
}

445. 两数相加 II

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例:

输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

既然不能改变链表的结构（翻转链表），那就用一个栈来保存链表中的值，可以做到逆向输出。
相加部分的代码逻辑就按常规思路写。

public ListNode addTwoNumbers (ListNode l1, ListNode l2) {
    Stack<Integer> l1Stack = listNodetoStack(l1);
    Stack<Integer> l2Stack = listNodetoStack(l2);
    int carry = 0;
    ListNode head = new ListNode(-1);
    while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) {
        int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();
        int y = l2Stack.isEmpty() ? 0 : l2Stack.pop();
        int sum = x + y + carry;
        ListNode node = new ListNode(sum % 10);
        carry = sum / 10;
        node.next = head.next;
        head.next = node;
    }
    return head.next;
}
private Stack<Integer> listNodetoStack (ListNode head) {
    Stack<Integer> stack = new Stack<>();
    while (head != null) {
        stack.push(head.val);
        head = head.next;
    }
    return stack;
}

725. 分隔链表

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。
这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。
返回一个符合上述规则的链表的列表。
举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]
示例 1：

输入: 
root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]
解释:
输入输出各部分都应该是链表，而不是数组。
例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。

示例 2：

输入: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解释:
输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。

提示:

• root 的长度范围： [0, 1000].
• 输入的每个节点的大小范围：[0, 999].
• k 的取值范围： [1, 50].

先统计出链表长度，除以 k, 求商和余数，其中：

• 余数代表最后结果中有多少个长链表
• 商代表每个短链表的长度（结果集中后部的链表）

• 长链表比短链表多一个节点

  public ListNode[] splitListToParts (ListNode root, int k) {
    ListNode cur = root;
    int len = 0;
    while (cur != null) {
        cur = cur.next;
        len++;
    }
    int mod = len % k;
    int size = len / k;
    cur = root;
    ListNode[] ans = new ListNode[k];
    for (int i = 0; cur != null && i < k; i++) {
        ans[i] = cur;
        int curSize = size + (mod-- > 0 ? 1 : 0);
        for (int j = 0; j < curSize - 1; j++) {
            cur = cur.next;
        }
        ListNode next = cur.next;
        cur.next = null;
        cur = next;
    }
    return ans;
  }
  

  328. 奇偶链表

  给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
  请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
  示例 1:

  输入: 1->2->3->4->5->NULL
  输出: 1->3->5->2->4->NULL
  

  示例 2:

  输入: 2->1->3->5->6->4->7->NULL 
  输出: 2->3->6->7->1->5->4->NULL
  

  说明:

• 应当保持奇数节点和偶数节点的相对顺序。

• 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

设置三个指针，其中奇指针和偶指针是很自然能想到的，evenHead起辅助作用，用于将奇链表和偶链表结合起来。

public ListNode oddEvenList (ListNode head) {
    ListNode odd = head;
    ListNode even = head.next;
    ListNode evenHead = even;
    while (even != null && even.next != null) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;
}

25 K个一组翻转链表