链表、栈、队列

链表 （2级标题）

1.反转链表（ LeetCode 206 ）（4级标题）

class Solution {
    
        public ListNode reverseList(ListNode head) {
    
            if (head == null)return null;
            ListNode pre = head;//前一个节点
            ListNode cur = pre.next;//当前要插入的节点
            ListNode next = null;//下一个待插入的节点
            pre.next = null;
            while (cur != null){
    
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;//pre即为最终的头节点（最后一个插入链表中的节点）
        }
    }

2.相交链表（ LeetCode 160 ）

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
            ListNode tempa = headA;
            ListNode tempb = headB;
            while (tempa != tempb){
    
                tempa = tempa == null ? headB : tempa.next;
                tempb = tempb == null ? headA : tempb.next;
            }
            return tempa;
        }
    }

3.合并两个有序链表 （ LeetCode 21 ）

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    
            ListNode cura = list1,curb = list2;
            ListNode res = new ListNode();
            ListNode tmp = res;
            while (cura != null && curb != null){
    //遍历
                if (cura.val < curb.val){
    
                    tmp.next = cura;
                    cura = cura.next;
                }else {
    
                    tmp.next = curb;
                    curb = curb.next;
                }
                tmp = tmp.next;
            }
            tmp.next = cura == null ? curb : cura;//处理剩余元素
            return res.next;
        }
    }

4.分隔链表 （ LeetCode 86 ）

    class Solution {
    
        public ListNode partition(ListNode head, int x) {
    
            ListNode minNode = new ListNode();
            ListNode maxNode = new ListNode();
            ListNode mintmp = minNode;
            ListNode maxtmp = maxNode;
            while (head != null){
    
                if (head.val < x){
    
                    mintmp.next = head;
                    mintmp = mintmp.next;
                }else {
    
                    maxtmp.next = head;
                    maxtmp = maxtmp.next;
                }
                head = head.next;
            }
            maxtmp.next = null;//防止环路
            mintmp.next = maxNode.next;
            return minNode.next;
        }
    }