LinkedList 简单算法题解析

LinkedList 算法题大纲

  • 反转单链表
  • 判断单链表是否是回文的
  • 判断链表是否有环
  • 移除单链表倒数第N个元素
  • 合并两个排序的单链表
  • 移除重复的元素从排序的链表当中
  • 链表当中删除指定值的节点
  • 删除当前链表节点
  • 交换链表节点的位置

反转单链表

反转一个单链表:

a -> b -> c -> d 反转后

d -> c -> b -> a

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
	//先在循环外设置个pre指针
    //循环head,每次都吧当前head的next指向pre
    //最后返回pre即可
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while(head != null) {
          ListNode tmp = head;
          head = head.next;
          tmp.next = pre;
          pre = tmp;
        }
        return pre;
    }
}

判断单链表是否是回文的

回文单链表如下,简单的描述回文就是正向读和逆向读是一样的就是回文:

1 -> 2 -> 3 -> 2 -> 1

解题思想:

  1. 利用快慢指针找到链表的中间元素
  2. 反转中间元素next后面是元素
  3. 比对head到中间元素以及中间元素到结尾是否相同
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode aft = reverse(slow.next);

        while(aft != null) {
            if (head.val != aft.val) {
                return false;
            }
            head = head.next;
            aft = aft.next;
        }

        return true;
    }


    private ListNode reverse(ListNode head) {
       ListNode pre = null;
       while(head != null) {
           ListNode tmp = head;
           head = head.next;
           tmp.next = pre;
           pre = tmp;
       }
       return pre;
    }
}

判断链表是否有环

解题思路:

使用快慢指针解决

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode fast = head.next;
        ListNode slow = head;

        while (fast != slow) {
            if (fast.next == null || fast.next.next == null) {
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }

        return true;
    }
}

移除单链表倒数第N个元素

解题思路:

  1. 先从head循环n次,判断是否n大于链表长度,如果大于直接返回head
  2. 如果n正好是链表长度,那么返回head的next,相当于删除第一个元素
  3. 如果n是其他情况,那么从当前位置指针向后移动,直到结尾,用另外一个head指针同时向后移动
  4. 最后把当前head指针的next元素删除掉就好
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode begin = head;
        ListNode end = head;

        for (int i = 0; i < n; i++) {
            if (end == null) {
                return head;
            }
            end = end.next;
        }

        if (end == null) {
            return head.next;
        }

        while (end.next != null) {
            begin = begin.next;
            end = end.next;
        }

        begin.next = begin.next.next;

        return head;
    }
}

合并两个排序的单链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 递归算法求解
 */
public class Solution {
  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;
      }
  }
}

移除重复的元素从排序的链表当中

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        while (current != null) {
            if (current.next != null && current.next.val == current.val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        return head;
    }
}

链表当中删除指定值的节点

Example:

Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6

Return: 1 –> 2 –> 3 –> 4 –> 5

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

删除当前链表节点

例如: 1 -> 2 -> 3 -> 4

传入的节点是 3 ,那么指向完后列表是 1 -> 2 -> 4

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void deleteNode(ListNode node) {
        if (node.next == null) {
            node = null;
        }
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

交换链表节点的位置

给定 1->2->3->4

返回 2->1->4->3

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;

        while (head.next != null && head.next.next != null) {
            ListNode t1 = head.next;
            ListNode t2 = head.next.next;

            head.next = t2;
            t1.next = t2.next;
            t2.next = t1;

            head = head.next.next;
        }

        return dummy.next;
    }
}

—EOF—

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章