对于链表的操作大多有迭代和递归两种解决方法：
迭代法：首先创建一个临时的节点p用于遍历链表，其开始可以指向头节点，也可以让其next节点指向头节点（（如果p指向头节点则while循环的判断条件是p!=null，反之则是p.next!=null），随后p不断地向后移动，在这个过程中进行要求的操作。如果结果要返回头指针，可以实现创建一个节点让其next指向头指针。
- 如果是要删除元素，那么需要拥有前一个节点的指针，让其指向要删除的元素的下一个元素，所以此时则不能让p指向头节点，而应该是让next去指向，即判断的是下一个元素的值，这样才能够实现删除。
- 如果是要翻转链表，那么需要不断改变指针的方向，即让next等于之前的元素，所以需要一个变量prev记录之前的元素，在循环内先将下一个元素保存到next变量之后再改变指针的指向，指向prev，然后将prev更改为p，将p更改为next，这样就能顺利遍历链表。
- 递归法：链表的递归实际上就是将链表拆为一个一个的子链表，不断缩小链表的长度，当到链表的最后一位（即p或p.next=null时），递归就到达了最底层，这时直接返回null或head。每一层递归传递给下一层的参数一般时子链表的头指针，拿到头指针后进行操作，之后根据题目要求进行操作并且返回上一层所需要的结果，一般是处理后新的头指针，用于给上一层的尾元素进行连接（比如进行交换顺序头指针发生改变时），或者一直返回最底层的指针（进行翻转头指针没有发生改变时（由于子链表的顺序没有改变，上一层可以直接拿到正确的下一个元素所以不需要下一层返回））
一、移出链表元素
题目链接：203.移出链表元素
/** * <pre> * <p>可以采用迭代，不断判断下一个节点是否要删除；或者采用递归，每次获取子链表的head，如果头节点的值如果等于val就说明返回的是子链表的头</p> * </pre> * * @author <a href="https://github.com/kil1ua">Ken-Chy129</a> * @date 2023/1/5 10:45 */ public class 移出链表元素203 { // 迭代 public ListNode removeElements(ListNode head, int val) { ListNode res = new ListNode(); res.next = head; ListNode p = res; while (p.next != null) { if (p.next.val == val) { p.next = p.next.next; } else { p = p.next; } } return res.next; } // 递归 public ListNode removeElements2(ListNode head, int val) { if (head == null) { return null; } head.next = removeElements2(head.next, val); // 每次删除子链表，返回子链表的头 return head.val == val ? head.next : head; } } class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } }
二、设计链表
题目链接：707.设计链表
/** * <pre> * <p>链表的设计：单链表和双链表</p> * </pre> * * @author <a href="https://github.com/kil1ua">Ken-Chy129</a> * @date 2023/1/5 11:29 */ // 单链表 class MyLinkedList { private int size; private MyListNode head; public MyLinkedList() { size = 0; head = new MyListNode(0); } public int get(int index) { if (index < 0 || index >= size) { return -1; } MyListNode p = head; for (int i=0; i<=index; i++) { p = p.next; } return p.val; } public void addAtHead(int val) { addAtIndex(0, val); } public void addAtTail(int val) { addAtIndex(size, val); } public void addAtIndex(int index, int val) { if (index < 0 || index > size) { return; } MyListNode p = head; for (int i=0; i<index; i++) { p = p.next; } MyListNode newNode = new MyListNode(val); newNode.next = p.next; p.next = newNode; size++; } public void deleteAtIndex(int index) { if (index < 0 || index >= size) { return; } MyListNode p = head; for (int i=0; i<index; i++) { p = p.next; } p.next = p.next.next; size--; } } class MyListNode { int val; MyListNode next; public MyListNode() { } public MyListNode(int val) { this.val = val; } public MyListNode(int val, MyListNode next) { this.val = val; this.next = next; } } // 双链表 class BiLinkedList { private int size; private BiListNode head; private BiListNode tail; public BiLinkedList() { size = 0; head = new BiListNode(0); tail = new BiListNode(0); head.next = tail; tail.prev = head; } public int get(int index) { if (index < 0 || index >= size) { return -1; } BiListNode p; if (index < size/2) { p = head; for (int i=0; i<=index; i++) { p = p.next; } } else { p = tail; for (int i=0; i<size-index; i++) { p = p.prev; } } return p.val; } public void addAtHead(int val) { addAtIndex(0, val); } public void addAtTail(int val) { addAtIndex(size, val); } public void addAtIndex(int index, int val) { if (index < 0 || index > size) { return; } BiListNode p; if (index < size/2) { p = head; for (int i=0; i<index; i++) { p = p.next; } } else { p = tail; for (int i=0; i<=size-index; i++) { p = p.prev; } } BiListNode newNode = new BiListNode(val); newNode.next = p.next; newNode.prev = p; p.next.prev = newNode; p.next = newNode; size++; } public void deleteAtIndex(int index) { if (index < 0 || index >= size) { return; } BiListNode p; if (index < size/2) { p = head; for (int i=0; i<index; i++) { p = p.next; } } else { p = tail; for (int i=0; i<=size-index; i++) { p = p.prev; } } p.next = p.next.next; p.next.prev = p; size--; } } class BiListNode { int val; BiListNode next; BiListNode prev; public BiListNode() { } public BiListNode(int val) { this.val = val; } }
三、翻转链表
题目链接：206.翻转链表
/** * <pre> * <p>翻转链表：迭代或递归</p> * </pre> * * @author <a href="https://github.com/kil1ua">Ken-Chy129</a> * @date 2023/1/5 13:39 */ public class 翻转链表206 { // 迭代法 public ListNode reverseList(ListNode head) { ListNode prev=null, p=head, next; while (p != null) { next = p.next; p.next = prev; prev = p; p = next; } return prev; } // 递归法 public ListNode reverseList2(ListNode head) { if (head == null || head.next == null) { // head == null 是用于0长度的链表直接返回 return head; // 遍历到最后一个节点则返回，这个就是翻转后链表的头 } ListNode newHead = reverseList2(head.next); // 如果是1->2->3->...->k->k+1->...->k+n // 执行到k时变为1->2->3->...->k->k+1<-...<-k+n // 那么k的next是k+1，需要将k+1的next改为k head.next.next = head; // 将k的next置为null，不然会成环，k指向k+1而k+1指向k head.next = null; return newHead; } }
四、两两交换链表中的节点
题目链接：24.两两交换链表中的节点
/** * <pre> * <p>可以采用迭代也可以采用递归</p> * </pre> * * @author <a href="https://github.com/kil1ua">Ken-Chy129</a> * @date 2023/1/5 14:58 */ public class 两两交换链表中的节点24 { public ListNode swapPairs(ListNode head) { ListNode p = new ListNode(), res = p; p.next = head; while (p.next != null && p.next.next != null) { ListNode first = p.next, second = p.next.next; first.next = second.next; second.next = first; p.next = second; p = first; } return res.next; } // 递归 public ListNode swapPairs2(ListNode head) { if (head == null || head.next == null) { return head; } ListNode next = swapPairs(head.next.next); ListNode second = head.next; head.next = next; second.next = head; return second; } }
