数据结构 链表 算法问题总结

public static class  ListNode{
    int val;
    ListNode next;
    ListNode(int x)
    {
        val =x;
        next =null;
    }
}

一、找出两个链表的交点(结点)

Leetcode

例如以下示例中 A 和 B 两个链表相交于 c1：

A:          a1 → a2
                    ↘
                      c1 → c2 → c3
                    ↗
B:    b1 → b2 → b3

1.while循环判断两链表下一结点是否相等,A链表走完走B链表，B链表走完走A链表，两者总长度相等，速度相同

2.循环退出的条件是两结点相等。

3.方法返回当前结点即为相交结点

 public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA ==null||headB==null)
    {
        return null;
    }
    ListNode you=headB;ListNode she=headA;

    while(you!=she)
    {
        you=you!=null?you.next:headA;
        she=she!=null?she.next:headB;
    }

    return you;
}

二、链表反转

Leetcode

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

1.头插法

2.先保存下一结点信息，头结点的指向重新分配，头结点插入在新节点的指向，下一结点重新为头结点

3.循环结束条件头结点不为空

public static intersect.ListNode reverseList(intersect.ListNode head){
    intersect.ListNode newHead=new intersect.ListNode(-1);

    while(head!=null)
    {
        intersect.ListNode next=head.next; //临时保存下一结点
        head.next =newHead.next;  //重新分配头结点的链接信息
        newHead.next=head;  //插入头结点
        head=next;      //下一结点作为头结点
    }
    return  newHead.next;
}

三、归并两个有序链表

Leetcode

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

1.递归

2.逐结点比较，比较两结点的大小，改变结点的指向，递归

public static intersect.ListNode mergeTwoLists(intersect.ListNode l1, intersect.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;
    }
}

四、从有序链表中删除重复节点

Leetcode

Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

1.递归

2.改变结点的指向，递归

3.比较结点是否相等决定返回当前结点还是下一结点

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) return head;
    head.next = deleteDuplicates(head.next);
    return head.val == head.next.val ? head.next : head;
}

五、删除链表的倒数第 n 个节点

Leetcode

Given linked list: 1->2->3->4->5, and n = 2.
output 1->2->3->5.

1.快慢结点结合

2.快结点

3.比较结点是否相等决定返回当前结点还是下一结点

public ListNode removeNthFromEnd(ListNode head, int n) {

    //思想，快慢结点结合，慢的结点减去先走的快结点就是倒数第n位结点
 ListNode fast=head;
 while(n-->0)
 {
     fast=fast.next;
 }
 if (fast==null)
   return head.next;
   ListNode slow=head;
   while(fast!=null && fast.next !=null)
   {
       fast=fast.next;
       slow=slow.next;
   }

   slow.next=slow.next.next;
   return head;
}

六、交换链表中的相邻结点

Leetcode

Given 1->2->3->4, you should return the list as 2->1->4->3.

1.先保存下一结点的信息

2.相邻结点的第一个结点的指向为下下下个结点

3.相邻结点的第二个结点的指向为第一个结点

public static intersect.ListNode swapPairs(intersect.ListNode head) {

    intersect.ListNode newNode=new intersect.ListNode(-1);
    newNode.next=head;

    intersect.ListNode pre=newNode;
    while(pre.next!=null&&pre.next.next!=null)
    {
        intersect.ListNode l1=pre.next;
        intersect.ListNode l2=pre.next.next;
        intersect.ListNode next=l2.next; //取对结点的下一结点作为后继结点，
        l1.next=next;    //添加在前一结点的后面
        l2.next=l1;      //将前一结点放在对节点中后一个结点的后面


        pre.next=l2; //重新赋值继续
        pre=l1;
    }

    return newNode.next;
}

七、链表求和

Leetcode

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 8 -> 0 -> 7

1.先用栈(先进后出)保存链表值的信息

2.出栈累加俩个栈顶的值，carry变量统计进位信息

3.细节，一个栈为空，另一个栈还有值时，给空栈赋值为0，对进位的元素取余作为当前结点的值，进位用carry变量保存。

public static intersect.ListNode addTwoNumbers(intersect.ListNode l1, intersect.ListNode l2) {
    Stack<Integer> l1Stack = buildStack(l1);
    Stack<Integer> l2Stack = buildStack(l2);
    intersect.ListNode head = new intersect.ListNode(-1);
    int carry = 0; //进位标志
    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;
        intersect.ListNode node = new intersect.ListNode(sum % 10);
        node.next = head.next;
        head.next = node; //头插法
        carry = sum / 10;
    }
    return head.next;
}

八、回文链表

Leetcode

输入: 1->2
输出: false

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

1.设置快慢结点，快结点走的比慢结点快2倍，快结点走完时，慢结点的位置位于总长的一半。

2.我们按慢结点的位置对链表进行分割。

3.将后半部分反转，与前半部分进行值的比较。

/**
 * 快慢结点的遍历，可以获取相应的链表长度
 * @param head
 * @return
 */
public static boolean isPalindrome(intersect.ListNode head) { //暴力解法，获取一半的长度，头插法反转后半部分，与前半部分的值进行比较
    if (head == null || head.next == null) return true;
    intersect.ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;//快结点的速度是慢结点的2倍，当快结点跑完的时候，慢结点的位置就是一半的长度
    }
    if (fast != null) slow = slow.next;  // 偶数节点，让 slow 指向下一个节点
    cut(head, slow);                     // 切成两个链表
    return isEqual(head, reverse(slow));
}

/**
 * 根据结点分开链表
 * @param head
 * @param cutNode
 */
private static void cut(intersect.ListNode head, intersect.ListNode cutNode) {
    while (head.next != cutNode) {
        head = head.next;
    }
    head.next = null;
}

/**
 * 头插法，反转链表
 * @param head
 * @return
 */
private static intersect.ListNode reverse(intersect.ListNode head) {
    intersect.ListNode newHead = null;
    while (head != null) {
        intersect.ListNode nextNode = head.next;
        head.next = newHead;
        newHead = head;
        head = nextNode;
    }
    return newHead;
}

九、分隔链表

Leetcode

Input:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]

1.分割的原理就是按分割的个数，断去最后一个结点的指向。

2.统计链表的长度，统计多余的长度放置首链表数组

3.每一段的个数循环下移，够了之后断开指向

   public static intersect.ListNode[] splitListToParts(intersect.ListNode root, int k) {
        int N = 0;
        intersect.ListNode cur = root;
        while (cur != null) {
            N++;
            cur = cur.next;
        }
        int mod = N % k;
        int size = N / k;
        intersect.ListNode[] ret = new intersect.ListNode[k];
        cur = root;
        for (int i = 0; cur != null && i < k; i++) {
            ret[i] = cur;
            int curSize = size + (mod-- > 0 ? 1 : 0);
            for (int j = 0; j < curSize - 1; j++) {
                cur = cur.next;   //下移
            }
            intersect.ListNode next = cur.next;
            cur.next = null;  //分割的原理是断链，断去指针的指向
            cur = next;
        }
        return ret;
    }

十、链表元素按奇偶聚集

Leetcode

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

1.改变结点的指向。

2.定义俩个头结点，奇元素的指向为当前元素的下下结点，偶元素(奇元素+1)的指向为下下结点

3.需要单独的保存一下偶结点的起始结点，为奇结点的最后一个结点的指向

public static intersect.ListNode oddEvenList(intersect.ListNode head) {
    if (head == null) {
        return head;
    }
    intersect.ListNode odd = head, even = head.next;
    intersect.ListNode evenHead = even; //保留偶数的起始点链表地址，因为even到后面会改变！

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

十一、思想总结

快慢结点，递归，头插法.